Meeting Rooms II (LeetCode 253)
You're given an array of meeting time intervals intervals, each entry [start_i, end_i]. Figure out the smallest number of conference rooms that lets every meeting happen -- no room may host two meetings whose times actually overlap (a meeting ending at end_i and another starting at start_j don't overlap once end_i <= start_j).
Worked Examples
intervals = [[0,30],[5,10],[15,20]]2[0,30] overlaps both other meetings, but those two do not overlap each other, so 2 rooms are enough.intervals = [[7,10],[2,4]]1⚖️Formal Constraints & Bounds
1 <= intervals.length <= 1040 <= start_i < end_i <= 106
Core Insight
A min-heap dynamically discovers and reuses the earliest-vacated room in logarithmic time.
Real-World Scenario & Production Applications
Cloud compute VM instance auto-scaling, conference room booking, and airport gate scheduling.
Step-by-Step Execution Trace Table
| Step | Meeting Interval | Rooms Heap Before | rooms[0] <= start? | Action Taken | Rooms Heap After | Active Room Count |
|---|---|---|---|---|---|---|
| 1 | [0, 30] | [] | — | Open Room 1 ending at 30 | [30] | 1 |
| 2 | [5, 10] | [30] | 30 <= 5 (False) | All rooms busy Open Room 2 | [10, 30] | 2 |
| 3 | [15, 20] | [10, 30] | 10 <= 15 (True) | Room 2 free! Pop 10, Push 20 (Reuse Room 2) | [20, 30] | 2 |
| 1 | events = [] |
| 2 | for start, end in intervals: |
| 3 | events.append((start, 1)) |
| 4 | events.append((end, -1)) |
| 5 | events.sort(key=lambda ev: (ev[0], ev[1])) |
| 6 | active_rooms = 0 |
| 7 | max_rooms = 0 |
| 8 | for time, delta in events: |
| 9 | active_rooms += delta |
| 10 | max_rooms = max(max_rooms, active_rooms) |
| 11 | return max_rooms |
Conceptual Narrative
Merge Intervals tracks continuous busy periods; Meeting Rooms II tracks peak concurrent overlap. Turning every meeting into a +1 event at its start and a -1 event at its end, then sweeping the sorted events, finds the minimum room count in O(N log N) time.
🧭 Conceptual Foundation & Pattern Intuition
The minimum number of conference rooms required equals the maximum number of meetings taking place concurrently at any single point in time. That number only changes at two kinds of moments: a meeting starts (one more room in use) or a meeting ends (one room freed). So we never need to know which room a meeting gets:
- Each interval
[start, end]becomes two events:(start, 1)and(end, -1). - Sort the events by time. On a tie, the
-1must come first: meetings are half-open[start, end), so a meeting ending at 10 frees its room before a meeting starting at 10 needs one. Sorting by(time, delta)does this, because-1 < 1. - Sweep the sorted events, adding each
deltatoactive_rooms. The largest valueactive_roomsever reaches (max_rooms) is the answer.
🚪 The Analogy: The Turnstile Counter
Picture a turnstile at the door of the meeting floor. Every time someone's meeting starts, the counter clicks up by one; every time a meeting ends, it clicks down by one. The building manager does not care who is in which room, only the highest number the counter ever showed during the day: that is how many rooms the floor needs. When one meeting ends at the exact moment another starts, the leaving group goes out before the arriving group comes in, so the counter does not rise by one for that instant.
🔑 Why It Works
Only the running count matters, so the start and end of the same meeting never need to stay together once they are events. The tie order is the one detail that is easy to get wrong: with starts first, [[5, 10], [10, 20]] would report 2 rooms instead of 1.
Sorting the intervals instead of the events: sorting
intervalsby start or by end does not order the individual start and end moments; build theeventslist first, then sort the events.Starts before ends on a tie: meetings are half-open
[start, end), so at a shared time the-1event must be applied before the+1. Sorting by(time, delta)does this because-1 < 1; putting starts first makes[[5, 10], [10, 20]]report 2 rooms instead of 1.Tracking room identities: the answer only needs the running count
active_rooms; each meeting becomes two independent events,(start, 1)and(end, -1), andmax_roomskeeps the highest count.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"The minimum number of conference rooms required": a room is needed for every meeting that is on at the same moment, so the answer is the largest number of meetings that overlap at any one time.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Decision rule: each event changes active_rooms by its delta, and right after every change max_rooms = max(max_rooms, active_rooms).
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Treating a meeting that ends at time T and one that starts at time T as overlapping: they can share the room. Sorting
eventsby time alone keeps whatever order they were appended in, so a start can be counted before the end it should replace; sort by(time, delta)so the-1comes first.Returning
active_roomsinstead ofmax_rooms: after the last event every meeting has ended, soactive_roomsis always0.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use a Sweep Line. Each meeting becomes two events: plus one at its start and minus one at its end. I sort the events by time and add them up in order, so the running total, active_rooms, is how many meetings are on at that moment, and its highest value, max_rooms, is how many rooms I need. That is correct because the count only changes at an event, so checking right after each event sees every value it ever takes. The trap is a tie: when one meeting ends as another starts, the minus one must come first, and sorting by time and then delta does that because minus one is smaller than plus one. Time is
O(N log N)for the sort, and space isO(N)for the 2N events."
Complexity & Mathematical Proof
O(N log N)
Look at the execution steps: the first loop appends two events per meeting, 2N appends in O(N). events.sort(key=lambda ev: (ev[0], ev[1])) sorts the 2N events in O(N log N). The last loop does O(1) work per event, 2N steps. The sort dominates.
O(N) Auxiliary
Look at memory allocations: events holds 2N tuples, O(N), and Python's sort may use up to O(N) more. Beyond that only the two counters active_rooms and max_rooms; the output is one integer.
T(N) = O(N) + O(2N log 2N) + O(2N) = O(N log N)
Derivation Progression
events.append((start, 1)); events.append((end, -1))
Two O(1) appends per meeting: O(N) for all N meetings.
events.sort(key=lambda ev: (ev[0], ev[1]))
Sorting 2N events takes O(N log N); on a tie the -1 sorts first.
active_rooms += delta; max_rooms = max(max_rooms, active_rooms)
O(1) per event, 2N events: O(N).
Variable Definitions
Total number of meeting intervals (2N events)
Memory Architecture & Bounds
O(1) Iterative
O(N) events list of 2N tuples
O(1) Peak room count integer
Boundary Best / Worst Cases
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "minimum number of conference rooms required", "maximum concurrent overlapping intervals". At production scale the same question is asked as peak concurrency: the most sessions, bookings or connections alive at one moment.
, so at most events. Time budget: for the sort. Space budget: for events.
A live stream of bookings cannot be sorted once up front. Re-sorting the whole events list on every new booking costs per insert; keep a sorted map from time to net delta instead, or count per time bucket when the time range is small.
Core Algorithmic State Invariants
- Only Event Times Matter
Between two event times nothing starts or ends, so the number of meetings in progress stays the same. Checking active_rooms right after each event therefore sees every value it ever takes, including the peak.
- The Peak Is Exactly the Room Count
At the peak moment max_rooms meetings are on at once, so no schedule can use fewer rooms. And giving each starting meeting any room that is free never needs more rooms than are busy at that moment, so max_rooms rooms are always enough.
- Counting, Not Assigning
events does not record which meeting each event came from, which is what keeps the sweep simple. If a problem also asks which room each meeting gets, the count alone is not enough: each meeting must be matched to a specific free room.
Meeting Rooms II (LeetCode 253)
You're given an array of meeting time intervals intervals, each entry [start_i, end_i]. Figure out the smallest number of conference rooms that lets every meeting happen -- no room may host two meetings whose times actually overlap (a meeting ending at end_i and another starting at start_j don't overlap once end_i <= start_j).
Worked Examples
intervals = [[0,30],[5,10],[15,20]]2[0,30] overlaps both other meetings, but those two do not overlap each other, so 2 rooms are enough.intervals = [[7,10],[2,4]]1⚖️Formal Constraints & Bounds
1 <= intervals.length <= 1040 <= start_i < end_i <= 106
Core Insight
A min-heap dynamically discovers and reuses the earliest-vacated room in logarithmic time.
Real-World Scenario & Production Applications
Cloud compute VM instance auto-scaling, conference room booking, and airport gate scheduling.
Step-by-Step Execution Trace Table
| Step | Meeting Interval | Rooms Heap Before | rooms[0] <= start? | Action Taken | Rooms Heap After | Active Room Count |
|---|---|---|---|---|---|---|
| 1 | [0, 30] | [] | — | Open Room 1 ending at 30 | [30] | 1 |
| 2 | [5, 10] | [30] | 30 <= 5 (False) | All rooms busy Open Room 2 | [10, 30] | 2 |
| 3 | [15, 20] | [10, 30] | 10 <= 15 (True) | Room 2 free! Pop 10, Push 20 (Reuse Room 2) | [20, 30] | 2 |
| 1 | events = [] |
| 2 | for start, end in intervals: |
| 3 | events.append((start, 1)) |
| 4 | events.append((end, -1)) |
| 5 | events.sort(key=lambda ev: (ev[0], ev[1])) |
| 6 | active_rooms = 0 |
| 7 | max_rooms = 0 |
| 8 | for time, delta in events: |
| 9 | active_rooms += delta |
| 10 | max_rooms = max(max_rooms, active_rooms) |
| 11 | return max_rooms |
Conceptual Narrative
Merge Intervals tracks continuous busy periods; Meeting Rooms II tracks peak concurrent overlap. Turning every meeting into a +1 event at its start and a -1 event at its end, then sweeping the sorted events, finds the minimum room count in O(N log N) time.
🧭 Conceptual Foundation & Pattern Intuition
The minimum number of conference rooms required equals the maximum number of meetings taking place concurrently at any single point in time. That number only changes at two kinds of moments: a meeting starts (one more room in use) or a meeting ends (one room freed). So we never need to know which room a meeting gets:
- Each interval
[start, end]becomes two events:(start, 1)and(end, -1). - Sort the events by time. On a tie, the
-1must come first: meetings are half-open[start, end), so a meeting ending at 10 frees its room before a meeting starting at 10 needs one. Sorting by(time, delta)does this, because-1 < 1. - Sweep the sorted events, adding each
deltatoactive_rooms. The largest valueactive_roomsever reaches (max_rooms) is the answer.
🚪 The Analogy: The Turnstile Counter
Picture a turnstile at the door of the meeting floor. Every time someone's meeting starts, the counter clicks up by one; every time a meeting ends, it clicks down by one. The building manager does not care who is in which room, only the highest number the counter ever showed during the day: that is how many rooms the floor needs. When one meeting ends at the exact moment another starts, the leaving group goes out before the arriving group comes in, so the counter does not rise by one for that instant.
🔑 Why It Works
Only the running count matters, so the start and end of the same meeting never need to stay together once they are events. The tie order is the one detail that is easy to get wrong: with starts first, [[5, 10], [10, 20]] would report 2 rooms instead of 1.
Sorting the intervals instead of the events: sorting
intervalsby start or by end does not order the individual start and end moments; build theeventslist first, then sort the events.Starts before ends on a tie: meetings are half-open
[start, end), so at a shared time the-1event must be applied before the+1. Sorting by(time, delta)does this because-1 < 1; putting starts first makes[[5, 10], [10, 20]]report 2 rooms instead of 1.Tracking room identities: the answer only needs the running count
active_rooms; each meeting becomes two independent events,(start, 1)and(end, -1), andmax_roomskeeps the highest count.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"The minimum number of conference rooms required": a room is needed for every meeting that is on at the same moment, so the answer is the largest number of meetings that overlap at any one time.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Decision rule: each event changes active_rooms by its delta, and right after every change max_rooms = max(max_rooms, active_rooms).
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Treating a meeting that ends at time T and one that starts at time T as overlapping: they can share the room. Sorting
eventsby time alone keeps whatever order they were appended in, so a start can be counted before the end it should replace; sort by(time, delta)so the-1comes first.Returning
active_roomsinstead ofmax_rooms: after the last event every meeting has ended, soactive_roomsis always0.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use a Sweep Line. Each meeting becomes two events: plus one at its start and minus one at its end. I sort the events by time and add them up in order, so the running total, active_rooms, is how many meetings are on at that moment, and its highest value, max_rooms, is how many rooms I need. That is correct because the count only changes at an event, so checking right after each event sees every value it ever takes. The trap is a tie: when one meeting ends as another starts, the minus one must come first, and sorting by time and then delta does that because minus one is smaller than plus one. Time is
O(N log N)for the sort, and space isO(N)for the 2N events."
Complexity & Mathematical Proof
O(N log N)
Look at the execution steps: the first loop appends two events per meeting, 2N appends in O(N). events.sort(key=lambda ev: (ev[0], ev[1])) sorts the 2N events in O(N log N). The last loop does O(1) work per event, 2N steps. The sort dominates.
O(N) Auxiliary
Look at memory allocations: events holds 2N tuples, O(N), and Python's sort may use up to O(N) more. Beyond that only the two counters active_rooms and max_rooms; the output is one integer.
T(N) = O(N) + O(2N log 2N) + O(2N) = O(N log N)
Derivation Progression
events.append((start, 1)); events.append((end, -1))
Two O(1) appends per meeting: O(N) for all N meetings.
events.sort(key=lambda ev: (ev[0], ev[1]))
Sorting 2N events takes O(N log N); on a tie the -1 sorts first.
active_rooms += delta; max_rooms = max(max_rooms, active_rooms)
O(1) per event, 2N events: O(N).
Variable Definitions
Total number of meeting intervals (2N events)
Memory Architecture & Bounds
O(1) Iterative
O(N) events list of 2N tuples
O(1) Peak room count integer
Boundary Best / Worst Cases
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "minimum number of conference rooms required", "maximum concurrent overlapping intervals". At production scale the same question is asked as peak concurrency: the most sessions, bookings or connections alive at one moment.
, so at most events. Time budget: for the sort. Space budget: for events.
A live stream of bookings cannot be sorted once up front. Re-sorting the whole events list on every new booking costs per insert; keep a sorted map from time to net delta instead, or count per time bucket when the time range is small.
Core Algorithmic State Invariants
- Only Event Times Matter
Between two event times nothing starts or ends, so the number of meetings in progress stays the same. Checking active_rooms right after each event therefore sees every value it ever takes, including the peak.
- The Peak Is Exactly the Room Count
At the peak moment max_rooms meetings are on at once, so no schedule can use fewer rooms. And giving each starting meeting any room that is free never needs more rooms than are busy at that moment, so max_rooms rooms are always enough.
- Counting, Not Assigning
events does not record which meeting each event came from, which is what keeps the sweep simple. If a problem also asks which room each meeting gets, the count alone is not enough: each meeting must be matched to a specific free room.