CareerCup

we can consider that the rectangles are axis-aligned .

The coordinates of left , right, top, bottom are in windows coordinate systems with origin at top left.

struct Rect
{
long left;
long right;
long top;
long bottom;
};

bool IntersectRect(Rect *R1, Rect *R2)
{
return (R2->left > R1->right || R2->right < R1->left || R2->top > R1->bottom || R2->bottom < R1->top);
}

If the rectangle intersects then the function IntersectRect returns false other wise true.

we can have have an array of all the rectangles drawn on the screen and shall compare all the drawn rectangles with the new rectangle to be drawn. If it intersect with any of the rectangles we shall not draw it.

updated the Note
Note: since all rectangles are x-axis aligned so for overlapping comparison we need to compare only a1 and a2 of new rectangle. Ignore b1 and b2.

@Susheel - I think you are wrong. Even if two rectangles have same x1 and x2, they can still be non-intersecting based on their y co-ordinate.

For ex.
Rectangles with bottom left (BL) and top right (TR) co-ordinate.

Rectangle 1 - BL = (3,1) TR = (6,4)
Rectangle 2 - BL = (3, 5) TR = (6, 8)

As you see both rectangles have same x co-ordinates but still if you draw them on cartesian-plane, they will be non-intersecting.

Hi Susheel, my observations here - I think you would need to maintain two sorted arrays ( one by x and one by y )

Try to insert the new rectangle into these sorted arrays.

Intersection will happen when
New Rectangle N overlaps with same rectangle R from existing list on both x and y axis.

Note that trying to insert this rectangle into the sorted array is O(N) operation.

So I am not sure if this method is any better than just checking against each rectangle by simple method.

Thoughts ?

If we assume that rectangles are X-axis aligned, we just need to check if their bottom sides overlap. So problem minimizes to line overlapping instead of rectangle overlapping.

We will keep two sorted arrays noting X coordinates of start and end points of bottom arm of rectangle.
say start[] and end []

Let bottom side of new rectangle be denoted by newstart, newend. Then algorithm can be :-

for (i=n)
    if ( newstart < end[i] ) 
           { if ( newend > start [i] )
                  //overlapping so exit
             else
                  // not overlapping so continue with next line
                  i--
             }
     else
        {   // line being compared is finished bfore new one. so no over lapping. 
          Print line. 
          Break loop
        }

Hi Nitin,
If the rectangles are aligned on x axis, how can BL be (3,1).. any bottom y-coordinate of x-axis aligned rectangle is 0. So the BL will always be (3,0) or in the form (Xi,0).

Hi DarkKnight,
because y-coordinate of bottom points is always 0, comparing x is always enough.
Also searching the position of new coordinates is O(log n), which is minimizing comparisons as asked in the question.

It is not mentioned that rectangles will keep coming, even if that is the case then we can use sorted ArrayList (which internally uses gap array kind of implementation) for efficient insertions.

Hi Susheel,

how can we make the assumption that "because y-coordinate of bottom points is always 0". The question says the rectangles are axis aligned, which means that the sides are parallel to the axis. Not necessarily on the axis.

I think you make a fair point that if we only have to check for 1 rectangle we can do it in log(n) time.

But note that sorting will take at o(nlogn) time.

So how is this method better than checking the new rectangle against each existing rectangle which will take O(n) time

Kaushik,
since we know the value of newstart and newend. Why do we need to do linear search. We can do binary search also and find two closest start and two closest end. just compare with the those 2 pairs.

fix : one should check if one of the four vertices(and not only two) of the ractangle lies inside the range of the given rectangle.

Why don't u search for a point in a range with 2 operations ?

A<=x<=B instead of using a range tree ( which is nothing but a fancy name for a segment tree ) ? 4 operations per element And there are n elements , 4*n*n operations in total which is reducible to 4*n if the elements are sorted . Sorting again makes about O(n log n) comparisons . Thus , total comparisions are O( 4*n log n + 4*n) . This I suppose is the minimum .

And we are searching for a range which could be as big as min and max. The range tree or the segment tree will be a complete tree with O(max-min +1) nodes at the lower most level . Thus, the height of the tree will be O( log (max - min +1) ).

when there are n elements and 4 operations per element, there itself you have the complexity of 4*n, how did you get 4*n*n?
Moreover if you do the brute force way, comparing all the rectangles the complexity would be O(n), why would anyone go for anything more than that?
I assume range tree helps finding elements between a range in O(logn). If we use 2D range tree how is it helping over 1D range tree? Because once we find range of x we don't need range of y, if we also look for range of y we end up with points in the rectangle