Sweep Line

Opening scenario

Problem references use LC for LeetCode.

Meeting Rooms II (LC 253): given meeting intervals [start, end), return the minimum number of rooms required so no two overlapping meetings share a room. Follow-up you should expect: The Skyline Problem (LC 218) — given buildings [left, right, height], output the skyline as a list of [x, height] key points.

Assume every meeting has start < end and every building has left < right and positive height. A skyline key point marks a position where the visible height changes, including a return to height 0 after the last building. Start by identifying the moments when the number of occupied rooms can change.

Question progression

Q1 — "Minimum rooms" = peak overlap. How do you find the peak without comparing every pair?

Question: Two meetings need different rooms only if they overlap; the answer is the maximum number of meetings active at the same instant. Comparing every pair of intervals for overlap is O(n²). What changes if you stop thinking about intervals and…