• Coding
  • Exercise - Overlapping Rectangle Sum

You are given a grid of integral values.
Ex:
0 1 2 3 4 5
6 7 8 9 0 1
1 3 5 7 9 1
5 6 5 6 5 6
In addition to its width and height.

You are asked to find the sum of the elements that fall inside the domain. The domain is defined as a list of rectangles that can overlap. Each rectangle is defined by four values: col (starting column), row(starting row), cols (width in columns), rows (height in rows).

An example domain to sum over for the above grid is:
Rectangle 1: 0 0 2 2
Rectangle 2: 1 1 2 2

The above two rectangles overlap on the single cell at coordinates (1, 1). The element in there should be added to the sum [strike]twice[/strike] once. The sum would then be: 0 + 1 + 6 + 7 + 8 + 3 + 5 = 30.
arithma wroteThe above two rectangles overlap on the single cell at coordinates (1, 1). The element in there should be added to the sum twice. The sum would then be: 0 + 1 + 6 + 7 + 8 + 3 + 5 = 30.
Wouldn't that be 0 + 1 + 6 + 7 + 7 +8 + 3 + 5 = 37?

This looks like a fun exercise, I'll see if I can put up some simple code to do it later on.
I think he meant it should be added once as it is an intersection.
@jsaade: You got it right.

The naive solution for the problem would be to go through each cell, check its inclusion-status in any of the rectangles, and then accordingly sum to a sentinel. I encourage you to see past that and try to solve for a performant algorithm (in possibly an infinite grid with arbitrarily large rectangles)
um shouldn't rectangle 1 be : 1 1 2 2 ?

cause in your case (0 0 2 2) rect1 would be :
0 1 2
6 7 8
1 3 5
and rect 2 would be :
7 8
3 5
so the overlap thing will be 7 8 3 5
and the sum will be 0 + 1 + 2 + 6 + 7 + 8 + 1 + 3 + 5 = ?? :P

or I did understand the thing wrong ?
rect1 (0 0 2 2) is
0 1 
6 7
rect2 (1 1 2 2) is
7 8
3 5
Look carefully at the definition of rectangles.