Question 209922 in Javascript Question posted in
A very good W3school tutorial can be found here.

What is the way forward without using just array loops to solve the colored rectangle problem in Javascript?

I have a coding assignment to do and I am stuck on this one question. I scoured the internet for potential solutions but they’re either paywalled or poorly solved.

I’m looking for a solution in JavaScript.

The question:

You are given N colorful rectangles, which are centered in the center of the Cartesian coordinate system and their sides are parallel to the coordinate axes. Each rectangle is uniquely identified with its width (along the x-axis) and height (along the y-axis)

Task
Determine the area of the colored part of the paper. In other words, determine the number of unit squares that belong to at least one rectangle

Example

Assumptions

N=3
Rectangle 1: [8,2] i.e width=8, height=2
Rectangle 2: [4,4] i.e width=4, height=4
Rectangle 3: [2,6] i.e width=2, height=6

The answer is 28

Function Description

Complete the function solve provided in the editor. This function takes the following 2 parameters and returns the area of the colored part of the paper

N represents the number of rectangles
arr represents Nx2 matrix containing the dimensions of N rectangles

Input Format

Note: This is the input format that you must use to provide custom input

The first line contains T denoting the number of test cases. T also specifies the number of times you have to run the solve function on a different set of inputs.

For each test case

The first line contains the integer N

Each of the following N lines contains two integers X and Y, dimensions (width and height, respectively) of the corresponding rectangles.

I tried using array methods but that’s just a small part of the solution? Completely stuck with this and any help is appreciated

Tags:

2

Answers


  1. 0

    Looking at the task, I assume that all of the widths and heights start off at the origin of the coordinate system.

    For the discrete case where input rectangles have only integer widths and heights (which appears to be your case), the problem could quite easily be solved by maintaining a set of all coloured points.

    For every rectangle in your input, you can try and generate a collection of distinct points that that rectangle covers. If you add all of these points to a set, all of the overlapping points will only be added once.

    The set would then contain all of the 1×1 grid squares which have been coloured by at least one of the input rectangles, so counting them up would ultimately give you the area.

    You might find this piece of documentation about sets to be useful. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set

    Login or Signup to reply.
  2. 0

    You could sort the input giving priority to wider rectangles, and then visit each rectangle in that order to add the slice that exceeds the previous rectangle’s height.

    That’s it:

    function solve(rects) {
    // Sort by descending width, descending height
    rects.sort((a, b) => b[0] - a[0] || b[1] - b[0]); 
    // Add horizontal slices to the total area
    let y = 0;
    let area = 0;
    for (const [width, height] of rects) {
        if (height <= y) continue; // This rectangle fits in a previous one: no effect
        area += (height - y) * width; // Add the part that sticks out vertically
        y = height;
    }
    return area;
}

// Two tests
console.log(solve([[8, 2], [4, 4], [2, 6]])); // 28
console.log(solve([[2, 10], [4, 4], [2, 2], [8, 8], [6, 6]])); // 68
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search