Algorithms / Interval Overlap Meeting Rooms
Least You Need to Know: Interval Overlap, Meeting Rooms, and End-Time Heaps
Some interval problems are not about choosing one compatible subset. Instead they ask for the maximum number of overlapping intervals at any moment, or equivalently the minimum number of rooms needed to host them all. A min-heap of end times tracks how many intervals are active right now.
Least you need to know
- Meeting rooms asks for the maximum simultaneous overlap, not the size of one non-overlapping subset.
- Sort intervals by start time, then compare each new start against the earliest ending active interval.
- If the earliest end time is finished before the new start, one room can be reused.
- A min-heap of active end times tracks current overlap efficiently.
- This is a different goal from interval scheduling maximize-count.
Key notation
- [s, f) — interval starting at s and ending at f
- active interval — an interval whose end time has not yet passed
- min-heap of end times — earliest finishing active interval at the root
Worked example
- Sort meetings by start time.
- Push the first meeting's end time into a min-heap.
- For each new meeting, compare its start to the smallest current end time.
- If that room is free, pop it; then push the new end time.
- The maximum heap size seen is the number of rooms needed.
Common mistakes
- Students often reuse earliest-finish interval scheduling even though the objective changed.
- Students often compare with the latest end time instead of the earliest one.
- Students often ignore interval endpoint conventions when deciding whether touching intervals overlap.
How to recognize it
- The prompt asks for minimum rooms, servers, or resources to host all intervals.
- You care about simultaneous activity, not one chosen subset.
- Each new interval should be compared to the earliest resource release time.
Next recommended lesson
Continue through this topic with Least You Need to Know: Interval Scheduling and Earliest-Finish Greedy.
Least You Need to Know: Interval Scheduling and Earliest-Finish GreedyRelated lessons
Keep going with nearby lessons in the same topic.