Meeting Rooms II

How it works

We want to find the minimum number of meeting rooms required so that no meetings overlap.

Instead of thinking in terms of rooms directly, we can think in terms of events on a timeline:

• when a meeting starts, we need one more room
• when a meeting ends, one room is freed

So the problem reduces to:

What is the maximum number of meetings happening at the same time?

If we track how the number of active meetings changes over time, the maximum value we ever reach is exactly the number of rooms we need.

This greedy approach works by:

• converting each meeting into two events (start and end)
• sorting all events by time
• sweeping from left to right while counting active meetings

Steps

1. Create an empty list time to store events.
2. For each meeting interval:
   • add (start, +1) → meeting starts (need a room)
   • add (end, -1) → meeting ends (free a room)
3. Sort time:
   • primarily by time
   • secondarily by event type so that end events (-1) are processed before start events (+1) at the same time
4. Initialize:
   • count = 0 → current number of ongoing meetings
   • res = 0 → maximum number of rooms needed
5. Traverse the sorted time list:
   • add the event value (+1 or -1) to count
   • update res = max(res, count)
6. After processing all events, return res.

Complexity

• Time complexity: O(n log n)
• Space complexity: O(n)

Things to watch for

Using the Wrong Comparison for Room Reuse

When checking if a room can be reused, the condition should be earliest_end_time <= current_start, not <. A meeting ending at time t allows a room to be reused by a meeting starting at time t.

Forgetting to Sort Meetings Before Processing

The min heap and two pointer approaches only work correctly when meetings are sorted by start time. Without sorting, you cannot determine the correct order of room allocation.

Returning the Max Heap Size Instead of Tracking It

The heap size changes throughout processing. You need to track the maximum size the heap reaches during iteration, or simply return the final heap size if you only pop when reusing rooms.

from typing import List

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        time = []
        for i in intervals:
            time.append((i[0], 1))
            time.append((i[1], -1))

        time.sort(key=lambda x: (x[0], x[1]))

        res = count = 0
        for t in time:
            count += t[1]
            res = max(res, count)
        return res

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        vector<pair<int, int>> time;
        for (const auto& i : intervals) {
            time.push_back({i[0], 1});
            time.push_back({i[1], -1});
        }

        sort(time.begin(), time.end(), [](auto& a, auto& b) {
            return a.first == b.first ? a.second < b.second : a.first < b.first;
        });

        int res = 0, count = 0;
        for (const auto& t : time) {
            count += t.second;
            res = max(res, count);
        }
        return res;
    }
};