Meeting Rooms II medium

Problem Statement

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

Example 1

Input: intervals = [[0,30],[5,10],[15,20]] Output: 2 Explanation: We need two meeting rooms:

• Room 1: [0,30]
• Room 2: [5,10], [15,20]

Example 2

Input: intervals = [[7,10],[2,4]] Output: 1 Explanation: We can use one meeting room:

• Room 1: [2,4], [7,10]

Steps

1. Sort the intervals: Sort the intervals based on their start times. This allows us to process meetings in chronological order.

2. Use a min-heap: A min-heap (priority queue) will store the end times of currently ongoing meetings. The heap's top element will always represent the meeting ending soonest.

3. Iterate through sorted intervals: For each interval:

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

4. Return the heap size: After processing all intervals, the size of the min-heap represents the minimum number of rooms required.

Explanation

The algorithm cleverly uses the min-heap to manage the ending times of ongoing meetings. By always having the earliest ending meeting at the top of the heap, we can efficiently determine whether a new room is needed or if an existing room can be reused. Sorting ensures that we consider meetings in the order they start, which is crucial for optimal room allocation.

Code

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int minMeetingRooms(vector<vector<int>>& intervals) {
    if (intervals.empty()) return 0;

    // Sort intervals by start time
    sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    });

    // Min-heap to store end times of ongoing meetings
    priority_queue<int, vector<int>, greater<int>> minHeap;

    // Process each interval
    for (const auto& interval : intervals) {
        int start = interval[0];
        int end = interval[1];

        // If a meeting has ended before the current meeting starts, reuse the room
        if (!minHeap.empty() && start >= minHeap.top()) {
            minHeap.pop();
        }
        // Add the current meeting's end time to the heap
        minHeap.push(end);
    }

    // The size of the heap is the minimum number of rooms needed
    return minHeap.size();
}

int main() {
    vector<vector<int>> intervals1 = {{0, 30}, {5, 10}, {15, 20}};
    cout << "Minimum meeting rooms needed (Example 1): " << minMeetingRooms(intervals1) << endl; // Output: 2

    vector<vector<int>> intervals2 = {{7, 10}, {2, 4}};
    cout << "Minimum meeting rooms needed (Example 2): " << minMeetingRooms(intervals2) << endl; // Output: 1

    return 0;
}

Complexity

• Time Complexity: O(N log N), dominated by the sorting of intervals. Heap operations are O(log N) each.
• Space Complexity: O(N) in the worst case, to store the min-heap (which can contain up to N elements if all intervals overlap).