Solution Explanation for Meeting Rooms II

This problem asks for the minimum number of conference rooms needed to accommodate a given set of meeting time intervals. The core idea revolves around efficiently tracking the number of rooms occupied at any given time. Two primary approaches are detailed below:

Approach 1: Using a Differential Array (Prefix Sum)

This approach cleverly uses a differential array to count the number of meetings starting and ending at each time point. The time complexity is O(n + t), where n is the number of intervals and t is the maximum time value which is given as 10^6. The space complexity is O(t) due to the differential array.

Algorithm:

1. Initialization: Create a differential array delta of size max_time + 1 (where max_time is the maximum end time among all intervals). Initialize all elements to 0.

2. Populate Delta: Iterate through each interval [start, end]. Increment delta[start] by 1 (meeting starts) and decrement delta[end] by 1 (meeting ends).

3. Prefix Sum: Perform a prefix sum on the delta array. This transforms the differential array into an array representing the number of concurrent meetings at each time.

4. Find Maximum: Find the maximum value in the transformed delta array. This maximum value represents the maximum number of concurrent meetings, which is the minimum number of rooms required.

Code (Python):

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        max_time = 0
        for start, end in intervals:
            max_time = max(max_time, end)
        delta = [0] * (max_time + 1)
        for start, end in intervals:
            delta[start] += 1
            delta[end] -= 1
        for i in range(1, max_time + 1):
            delta[i] += delta[i - 1]
        return max(delta)
 

Code (Java):

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        int maxTime = 0;
        for (int[] interval : intervals) {
            maxTime = Math.max(maxTime, interval[1]);
        }
        int[] delta = new int[maxTime + 1];
        for (int[] interval : intervals) {
            delta[interval[0]]++;
            delta[interval[1]]--;
        }
        int maxOverlap = 0;
        int currentOverlap = 0;
        for (int i = 0; i <= maxTime; i++) {
            currentOverlap += delta[i];
            maxOverlap = Math.max(maxOverlap, currentOverlap);
        }
        return maxOverlap;
    }
}

Code (C++):

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        int maxTime = 0;
        for (const auto& interval : intervals) {
            maxTime = max(maxTime, interval[1]);
        }
        vector<int> delta(maxTime + 1, 0);
        for (const auto& interval : intervals) {
            delta[interval[0]]++;
            delta[interval[1]]--;
        }
        int maxOverlap = 0;
        int currentOverlap = 0;
        for (int i = 0; i <= maxTime; i++) {
            currentOverlap += delta[i];
            maxOverlap = max(maxOverlap, currentOverlap);
        }
        return maxOverlap;
    }
};

Time Complexity Analysis: O(n + t) where n is the number of intervals and t is the maximum time value. The dominant operations are iterating through the intervals (O(n)) and performing the prefix sum (O(t)).

Space Complexity Analysis: O(t). The space used is dominated by the delta array.

Approach 2: Using a Priority Queue (Min-Heap)

This approach uses a min-heap to track the end times of meetings currently in progress. This approach has a time complexity of O(n log n), where n is the number of intervals, because of sorting. The space complexity is O(n) in the worst case, if all intervals overlap.

Algorithm:

1. Sort: Sort the intervals by their start times.

2. Min-Heap: Initialize a min-heap (priority queue) to store the end times of ongoing meetings.

3. Iterate: Iterate through the sorted intervals:

   • If the current interval's start time is greater than or equal to the earliest end time (the top element of the min-heap), it means we can reuse a room. Remove the earliest end time and add the current interval's end time to the heap.
   • Otherwise, a new room is needed. Add the current interval's end time to the heap.

4. Result: The size of the min-heap at the end of the iteration represents the minimum number of rooms required.

Code (Python):

import heapq
 
class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        intervals.sort()
        heap = []
        for start, end in intervals:
            if heap and start >= heap[0]:
                heapq.heapreplace(heap, end)
            else:
                heapq.heappush(heap, end)
        return len(heap)

Time Complexity Analysis: O(n log n) because of sorting. The heap operations take O(log n) time each.

Space Complexity Analysis: O(n) in the worst case (all intervals overlap). The heap can hold up to n elements.

The choice between these two approaches depends on the specific constraints of the problem. If the maximum time is relatively small, the differential array approach might be slightly faster. However, for larger time ranges, the min-heap approach offers better scaling. The min-heap approach is generally more versatile and preferred unless there is specific knowledge about the problem constraints.