Given \(N\) rectangles, find all the intersections.
This algorithm is very similar to the 1-D line intersection search. The difference here is that instead of storing the y-coordinate, we store the \(y\) interval on the vertical axis every time we hit a left edge. Whenever we hit a left edge, we check for an interval intersection. When we hit a right edge, we remove the interval.
The algorithm takes \(O(N\log N+R\log N)\) where \(R\) is the number of intersections.