Maximum rectangle overlapping point

Question

Given the coordinates of N rectangles (N<=100.000) in the grid L*C (L and C can range from 0 to 1.000.000.000) I want to know what is the maximum number of rectangle overlapping at any point in the grid.

So I figured I would use a sweeping algorithm, for each event (opening or ending of a rectangle) sorted by x value, I add or remove an interval to my structure.

I have to use a tree to maintain the maximum overlapping of the intervals, and be able to add and remove an interval.

I know how to do that when the values of the intervals (start and end) are ranging from 0 to 100.000, but it is impossible here since the dimensions of the plane are from 0 to 1.000.000.000. How can I implement such a tree?

Answer 1

If you know the coordinates of all the rectangles up-front, you can use "coordinate compression".

Since you only have 10^5 rectangles, that means you have at most 2*10^5 different x and y coordinates. You can therefore create a mapping from those coordinates to natural numbers from 1 to 2*10^5 (by simply sorting the coordinates). Then you can just use the normal tree that you already know for the new coordinates.

This would be enough to get the number of rectangles, but if you also need the point where they overlap, you should also maintain a reverse mapping so you can get back to the real coordinates of the rectangles. In the general case, the answer will be a rectangle, not just a single point.

Answer 2

Use an interval tree. Your case is a bit more complicated because you really need a weighted interval tree, where the weight is the number of open rectangles for that interval.