Sweep Line and Intervals
Turn intervals into start and end events, sort them, and sweep left to right to count overlaps, merge ranges and handle huge coordinates.
The problem
You have intervals on a number line, for example meetings with a start and end time. Questions of this kind come up again and again:
- What is the largest number of intervals that overlap at one moment?
- If I merge all overlapping intervals, what remains?
- For each , how many points are covered by exactly intervals?
1 of 10