Sign in to watch this lesson
Algorithms - Greedy · 4:14
Sweep Line
When every meeting must happen, the number of rooms needed is the largest number running at once. We turn the meetings [1,4) [2,5) [3,6) [5,7) [6,8) into +1/-1 events, sweep them in time order with ends before starts at equal times, and watch the count peak at 3; the wrong tie order reports two rooms for two back-to-back meetings. A min-heap of free times then assigns the rooms, reusing them as they free up. We connect the sweep to difference arrays, time two million events on this Mac, and handle the live-feed version with a heap of close times.
You will learn
- Turn intervals into +1/-1 events, sort them and sweep to find the peak number of overlapping intervals in O(n log n)
- Order events correctly at equal times (ends before starts for half-open intervals) and convert inclusive days to half-open
- Assign the minimum number of rooms with a min-heap of (free time, room), and explain why the peak is also a lower bound
- Relate the sweep to difference arrays and maintain a live open count over a time-ordered stream with a heap of close times