[Algorithm][Geometry] Sweep line algorithm

Problems:

• 218. The Skyline Problem: https://leetcode.com/problems/the-skyline-problem/description/
• 253. Meeting Rooms II: https://leetcode.com/problems/meeting-rooms-ii/description/
• 850. Rectangle Area II: https://leetcode.com/contest/weekly-contest-88/problems/rectangle-area-ii/

---

Articles: https://leetcode.com/articles/rectangle-area-ii/

• Moving the sweep line
• Sweeping algorithms typically manage two sets of data:
• The sweep-line status gives the relationships among the objects intersected by the sweep line.
• The event-point schedule is a sequence of x-coordinates, ordered from left to right, that defines the halting positions of the sweep line. We call each such halting position an event point. Changes to the sweep-line status occur only at event points.
• The sweep-line status is a total preorder T:
• INSERT(T, s): insert segment s into T.
• DELETE(T, s): delete segment s from T.
• ABOVE(T, s): return the segment immediately above segment s in T.
• BELOW(T, s): return the segment immediately below segment s in T.

Any-segments-intersect algorithm:
ANY-SEGMENTS-INTERSECT(S)

1. T -> {}
2. sort the endpoints of the segments in S from left to right, breaking ties by putting points with lower y-coordinates first 
3. for each point p in the sorted list of endpoints
4.     if p is the left endpoint of a segment s
5.     then INSERT(T, s)
6.     if (ABOVE(T, s) exists and intersects s) or (BELOW(T, s) exists and intersects s)
7.         then return TRUE
8.     if p is the right endpoint of a segment s
9.         if both ABOVE(T, s) and BELOW(T, s) exist and ABOVE(T, s) intersects BELOW(T, s)
10.             return TRUE
11.         DELETE(T, s)
12. return FALSE

---

Java:

• TreeMap: https://docs.oracle.com/javase/8/docs/api/java/util/TreeMap.html
• Example: https://leetcode.com/problems/rectangle-area-ii/discuss/137941/Java-TreeMap-solution-inspired-by-Skyline-and-Meeting-Room
• Segment tree with lazy propagation (custom)
• https://leetcode.com/articles/a-recursive-approach-to-segment-trees-range-sum-queries-lazy-propagation/