Sweep-Line & Concurrent Peak Counting

Foundations

In the first lesson, overlapping intervals were merged into ranges. Now, what if the overlaps must be counted instead: at the busiest moment, how many intervals are active at once?

A sweep line turns intervals into events, +1 at each start and -1 at each end, visited in time order. A running count of active intervals rises and falls with the events, and its maximum is the peak overlap. Equivalently, sort the starts and the ends separately and walk both, or keep a min-heap of the active ends and drop every end at or before the next start. Each costs O(n log n) for the sort.

For intervals = [[1, 4], [6, 9], [2, 5], [8, 11], [7, 10]], the starts are 1, 2, 6, 7, 8 and the ends 4, 5, 9, 10, 11. The count climbs to 2 at time 2 and falls to 0 by 5, then climbs to 3 at time 8, when [6, 9], [7, 10], and [8, 11] are all active. The peak is 3.

• Heap

  The active intervals' end times sit in a min-heap. That lesson covers heapq.

  Open lesson

Case Scenario

Meeting Rooms II gives meetings as half-open intervals [start, end) and asks for the fewest rooms that hold them all. That is the peak overlap: at the busiest moment, every active meeting needs its own room. A min-heap of end times frees a room whenever its meeting has ended by the next start. For intervals = [[0, 30], [5, 10], [15, 20]], the answer is 2.

The direct approach checks every start time and counts how many meetings are running at that moment, scanning the whole list each time: O(n²) comparisons. With 100,000 meetings that is 10 billion checks, though after a sort, meetings that end before a start can simply be dropped in order.