π Problem Details
- Title:
253. Meeting Rooms II
- Link: https://leetcode.com/problems/meeting-rooms-ii/
- Difficulty: Medium
- Tags/Categories: Intervals
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();
}
};