LeetCode Solution 253 - Meeting Rooms II

Problem Statement

Given an array of meeting time intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.

Constraints:

• 1 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= starti < endi <= 10^6

Optimal Approach

To determine the minimum number of rooms required, we use the Min-Heap (Priority Queue) approach:

1. Sort intervals by start time.
2. Use a Min-Heap to track meeting end times.
3. Process intervals by adding new meetings and removing finished ones.

LeetCode-Compatible C++ Solution (Min-Heap Approach)

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        if (intervals.empty()) return 0;
        
        sort(intervals.begin(), intervals.end());
        priority_queue<int, vector<int>, greater<int>> minHeap;
        
        for (const auto& interval : intervals) {
            if (!minHeap.empty() && minHeap.top() <= interval[0]) {
                minHeap.pop();
            }
            minHeap.push(interval[1]);
        }
        return minHeap.size();
    }
};

Step-by-Step Explanation of Code

1. Sort the intervals based on start time.
2. Use a min-heap to keep track of meeting end times.
3. Iterate through the intervals:
   • If a meeting has ended (minHeap.top() <= interval[0]), remove it from the heap.
   • Add the new meeting's end time to the heap.
4. Heap size represents the max number of overlapping meetings, which is the required rooms count.

Dry Run / Execution Steps

Example Input:

intervals = {{0,30}, {5,10}, {15,20}}

Execution Steps:

1. Sort intervals → {{0,30}, {5,10}, {15,20}}.
2. Push 30 into min-heap.
3. Compare {5,10}: No available room → Push 10.
4. Compare {15,20}: Room 10 is free → Remove 10, push 20.
5. Result: 2 rooms required.

Alternative Approaches

1. Brute Force (Checking Overlaps for Every Pair)

• Compare all intervals to count overlaps.
• Time Complexity: O(N^2)
• Space Complexity: O(1)
• Why not? Inefficient for large inputs.

2. Sorting + Two Pointers (Sweep Line Algorithm)

• Sort start and end times separately.
• Use two pointers to track overlapping meetings.
• Time Complexity: O(N log N)
• Space Complexity: O(N)
• Why not? Uses extra space for separate arrays.

Why Min-Heap is Best?

Approach	Time Complexity	Space Complexity	Feasibility
Brute Force	O(N^2)	O(1)	❌ Infeasible
Two Pointers	O(N log N)	O(N)	✅ Efficient
Min-Heap	O(N log N)	O(N)	✅ Best Choice

Min-Heap is optimal because it efficiently tracks overlapping meetings with O(N log N) time and O(N) space.

Conclusion

The Min-Heap Approach is the best choice for solving this problem as it efficiently tracks meeting end times and determines the number of rooms required.

Similar Problems for Practice

• Meeting Rooms (LeetCode 252)
• Non-overlapping Intervals (LeetCode 435)
• Minimum Number of Arrows to Burst Balloons (LeetCode 452)