🌱 Keegan's Digital Garden

253. Meeting Rooms II

2 min read

📝 Problem Details

input array intervals where each interval [start,end] represents a meeting return the minimum number of conference rooms required

💭What Were My Initial Thoughts?

- we need to sort the meetings by their start time 
- need to track ongoing meetings to determine when a room becomes available
- A **min-heap (priority queue)** can be used to keep track of meeting end times:
  - If a new meeting starts after the earliest ending meeting, reuse that room.
  - Otherwise, allocate a new room.

💡 Explanation of Solution

1. sort the intervals by start time
2. use a min heap to track end times of meetings currently occupying rooms
3. iterate through the meetings
   - if the current meeting starts **after or when** the earliest ending meeting finishes, reuse that room (pop from heap).
   - always push the current meeting's end time to the heap
4. the size of the heap at any point gives the minimum number of rooms required

⌛ Complexity Analysis

Time Complexity: O(n log n) due to sorting and heap operations
Space Complexity: O(n) for storing elements in the heap

💻 Implementation of Solution

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        if (intervals.empty()) return 0;
 
        // Sort meetings by start time
        sort(intervals.begin(), intervals.end());
 
        // Min-heap to track end times of ongoing meetings
        priority_queue<int, vector<int>, greater<int>> minHeap;
 
        for (const auto& meeting : intervals) {
            // If the room is free (earliest meeting ended), remove it from heap
            if (!minHeap.empty() && minHeap.top() <= meeting[0]) {
                minHeap.pop();
            }
 
            // Add the current meeting's end time to the heap
            minHeap.push(meeting[1]);
        }
 
        // Heap size represents the number of rooms needed
        return minHeap.size();
    }
};

Graph View