PROBLEM LINK:
Editorialist: Karan Aggarwal
DIFFICULTY:
MEDIUM
PREREQUISITES:
Line Sweep, Lazy Propagation, Segment-trees, Coordinate Compression.
PROBLEM:
Given a set of N axis-aligned rectangles, tell the maximum number of rectangles that overlap, at any point.
EXPLANATION:
This problem requires the use of line sweep. Similar common problems like finding the area of union of rectangles, etc can be solved using line sweep.
We are using either vertical or horizontal line sweep here. Radial and angular sweeps are also common.
Along with the line sweep, we will maintain an active set of rectangles to solve this problem.
The idea here is that if we do a vertical line sweep, each rectangle has two events: left edge and right edge. When we cross the left edge, the rectangle is added to the active set. When we cross the right edge, it is removed from the active set.
Now we only need to consider the maximum number of rectangle overlap, during these event points (adding or removing the edges).
We can determine the maximum number of overlapping rectangles by running the same algorithm in an inner loop, but rotated 90 degrees. Ignore the inactive rectangles, and consider a horizontal sweep line that moves top-down. The events are now the horizontal edges of the active rectangles, and every time we cross one, we can simply increment or decrement a counter that says how many rectangles overlap at the current point. The maximum value of the counter at any point of time, will be the answer. This gives a complexity of O(N * N). But we can use a segment tree with lazy propagation and modify the task to a collection of range addition and range max query. Thus a separate inner loop will not be required reducing the complexity to (N * logN).
Sort the start and end X coordinates of all the rectangles. For each X coordinate, also store the corresponding start and end Y coordinates that it covers and whether it marks the start or end of a rectange. Now process these sorted X coordinates in increasing order.
For every x-coordinate that marks the start of the rectange, add 1 to corresponding range of y in a segment tree. For every x-coordinate that marks the end of the rectangle, add -1 to the corresponding range of y in the segment tree. After every insert into the segment tree, query for the maximum element in the segment tree. Keep track of the maximum such value and at the end, this value will be the required answer.
Since the coordinates can lie from -10^8 to 10^8, implementing the above is infeasible since one cannot declare a segment tree of such a large size. Hence, prior to executing the above algorithms, all coordinates must be reduced in the range 1 to 2*N. Note that this compression is possible because the actual values of the coordinates don’t matter, only their relative ordering is of importance. So, we can sort all the coordinates and then provide them value based on their index of the sorted array. Then, building a segment tree on Y coordinate is feasible since N <= 10^4.
Or we can use a implicit segment tree with lazy propagation. Then we don’t require coordinate compression.
Complexity : O(N * logN)