Meeting Rooms II — Greedy + Heap

The min-heap of end times

Given meeting intervals, how few rooms cover them all? The greedy plan: process meetings in order of start time. Keep a min-heap of the end times of rooms currently in use, so the room that frees up soonest is always on top.

For each meeting, peek the heap. If its earliest end time is ≤ this meeting's start, that room is free: reuse it (pop, push the new end). Otherwise every room is busy: open a new one (push). The answer is the largest the heap ever grows.

// sort meetings by start
for [s, e] in meetings:
  if heap && heap.top() <= s:
    heap.pop() # reuse a room
  heap.push(e)
answer = max(answer, heap.size())

Time Complexity

O(N log N)

Sorting dominates; each meeting does O(log N) heap work.

Space Complexity

O(N)

Worst case every meeting overlaps and the heap holds all N end times.

Live Visualization

meetings = format: [start,end] [start,end] …

Current meeting Reused a room Opened new room Room end-time in heap

Meetings on a timeline (sorted by start)

Rooms in use min-heap of end times

meeting = – earliest free = – rooms now = 0 max rooms = 0

Step 0 / 0

Current meeting

–

[start, end]

Earliest free

–

heap top (end)

Rooms in use

heap size

Max needed

the answer

Enter meetings and hit Play to watch rooms open and get reused.

✓ Done Speed

Step-by-step trace

#	Action	Meeting	Heap top	Heap (end times)	Rooms	Max

C++ — Meeting Rooms II (LC 253)

int minMeetingRooms(vector<vector<int>>& meetings) {
    if (meetings.empty()) return 0;

    // 1) sort by start time
    sort(meetings.begin(), meetings.end());

    // 2) min-heap of end times of rooms in use
    priority_queue<int, vector<int>, greater<>> pq;

    for (auto& m : meetings) {
        int s = m[0], e = m[1];
        // earliest-freeing room is done ⇒ reuse it
        if (!pq.empty() && pq.top() <= s) pq.pop();
        pq.push(e);            // occupy a room until e
    }
    return pq.size();   // rooms still needed = peak overlap
}

📝 My Notes ●

▾

Saved 0 chars