DevOps NetworkDevOpsNetwork
Join Free
Advanced

Meeting Rooms II

mediumHeaps (hard) Must-do

Problem statement

You get two arrays, start and end, where start[i] and end[i] are the start and end time of the ith meeting. Find the minimum number of meeting rooms needed so that every meeting can happen — no two meetings that genuinely overlap can share a room, but a meeting is allowed to start in a room the exact instant another meeting in that room ends.

That last rule matters: if one meeting ends at time 10 and another starts at time 10, they don't need separate rooms — they can be treated as back to back in the same room, not as overlapping.

Think of start/end as reservation windows for a shared resource — a build agent, a GPU, a deploy slot — and the question as "what is the fewest number of these resources we'd need so nothing ever has to wait?"

Examples

Example 1

Input: start = [1, 10, 7], end = [4, 15, 10]

Output: 1

Explanation: The meetings are [1,4], [10,15], and [7,10]. [7,10] and [10,15] touch at 10 but don't truly overlap, so they can share a room; [1,4] doesn't overlap either of them. One room is enough for all three.

Example 2

Input: start = [2, 9, 6], end = [4, 12, 10]

Output: 2

Explanation: The meetings are [2,4], [9,12], and [6,10]. [6,10] and [9,12] genuinely overlap (9 is strictly less than 10), so they need separate rooms. [2,4] doesn't overlap either, so it can reuse whichever room is free. Two rooms are needed at the peak.

Hints

Hint 1: The answer is really asking: at the single busiest moment across the whole day, how many meetings are happening at once? That peak count is exactly the number of rooms needed.

Approach

Optimal: Min-heap of room end times

Intuition

Process meetings in order of when they start. Keep a min-heap of the end times of every meeting currently occupying a room — the smallest value on top is whichever room is due to free up soonest. For each new meeting, check that soonest-freeing room: if its end time is already at or before the new meeting's start time, that room is free and can be reused (pop the old end time, push the new one in its place). Otherwise, every currently occupied room is still busy, so a brand new room is needed (just push the new end time without popping). At the end, the number of end times left in the heap is exactly the number of rooms that ended up in simultaneous use.

Steps

  1. Sort the meetings by start time (pairing each start with its end).
  2. Keep a min-heap of end times, initially empty.
  3. For each meeting (s, e) in start-time order: if the heap isn't empty and its smallest end time is <= s, pop that end time — its room is free and about to be reused.
  4. Push e onto the heap either way — either as the new occupant of the just-freed room, or as a brand new room's occupant if nothing was popped.
  5. After every meeting has been processed, the heap's size is the answer.

Dry run

start = [2, 9, 6], end = [4, 12, 10] → sorted by start: (2,4), (6,10), (9,12)

meeting heap before soonest end ≤ start? pop? heap after push
(2,4) {} heap empty, no no {4}
(6,10) {4} 4 ≤ 6, yes pop 4 {10}
(9,12) {10} 10 ≤ 9? no no {10, 12}

Final heap size: 2, matching both earlier approaches.

Edge cases: the very first meeting always finds an empty heap, so nothing is popped and one room is opened — the general rule handles this without a special case. Two meetings that only touch (one's end equals the next one's start) correctly trigger a reuse, since the pop condition is heap top <= s, not a strict <.

Complexity

Time O(n log n) — sorting the meetings by start time is O(n log n); the sweep afterward does at most one heap push and one heap pop per meeting, each O(log n).

Space O(n) — the heap can hold up to n end times in the worst case (every meeting overlapping every other).

import heapq
from typing import List


class Solution:
    def minMeetingRooms(self, start: List[int], end: List[int]) -> int:
        meetings = sorted(zip(start, end))
        heap = []  # end times of meetings currently occupying a room
        for s, e in meetings:
            if heap and heap[0] <= s:
                heapq.heapreplace(heap, e)
            else:
                heapq.heappush(heap, e)
        return len(heap)


if __name__ == "__main__":
    print(Solution().minMeetingRooms([1, 10, 7], [4, 15, 10]))
    print(Solution().minMeetingRooms([2, 9, 6], [4, 12, 10]))

Interview follow-ups

  • What if you also needed to know which specific room each meeting was assigned to, not just how many rooms are needed?

    The min-heap approach already computes this almost for free: instead of a heap of bare end times, use a heap of (end time, room id) pairs. When reusing a room, the popped entry's room id is the one to assign to the new meeting; when opening a new room, hand out the next unused room id. The overall room count and time complexity stay exactly the same — this is just carrying one more piece of information through the same algorithm.

  • The meetings arrive one at a time as a live stream (new bookings keep coming in), and you need to know the current number of rooms in use at any moment, not compute it once for a fixed list.

    Keep the same min-heap of active end times as a persistent structure across calls rather than rebuilding it from scratch. Each new booking triggers the same reuse-or-open check against the heap's current state, and separately, on a timer, expired meetings whose end time has passed without a new booking taking their room can be lazily removed by checking the heap's top against the current time — the same "check the earliest end time" idea used in the batch algorithm applies incrementally, one booking or one clock tick at a time.

Frequently asked questions

Once the times are separated into two independent sorted lists, the sweep only needs to answer a simpler question at each step — "does the next start happen before the next end, across everyone?" — without caring which specific meeting either time belongs to. Since the count of overlapping meetings only depends on how many starts have occurred versus how many ends have occurred by a given moment, not on which meeting is which, the pairing information isn't needed once you're only tracking a running count.

The heap approach processes meetings one at a time, in the order they start, and needs to know each specific meeting's own end time when deciding whether to push it as a new room or reuse a freed one — it's building an actual room assignment (implicitly), not just counting. Because of that, it genuinely needs to know which end time belongs to which incoming meeting, unlike the two-pointer approach, which only ever compares "the next start" against "the next end" as two independent streams.

If the heap's smallest end time equals the current meeting's start time exactly, that room's previous meeting has just finished — by the problem's own rule, a new meeting can begin there immediately. Using <= lets that reuse happen; using a strict < would wrongly treat that touching moment as still occupied and force an unnecessary new room to be opened.

Deciding the minimum number of concurrent resources needed — build agents, database connections, deploy slots — to serve a known set of overlapping demand windows is exactly this problem, and the min-heap version doubles as a genuine room/resource assignment algorithm, not just a room count.