Meeting Rooms II

Given a list of meeting intervals, represented as pairs of integers [start, end], where start denotes the start time of the meeting and end denotes the end time of the meeting, find the minimum number of meeting rooms required to hold all the meetings without any overlaps.

Example:

Input:

meetings = [[0, 30], [5, 10], [15, 20]]

Output:

2

Explanation: In the input, there are three meetings with intervals [0, 30], [5, 10], and [15, 20]. To hold all the meetings without any overlaps, at least two meeting rooms are required. For example, meeting [0, 30] and [5, 10] can be held in one room, and meeting [15, 20] can be held in another room.

Meeting Rooms II Solution in C++:

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

// Function to find the minimum number of meeting rooms required
int minMeetingRooms(std::vector<std::vector<int>>& meetings) {
    // Sort the meetings based on their start time in ascending order
    std::sort(meetings.begin(), meetings.end(), [](const auto& a, const auto& b) {
        return a[0] < b[0];
    });

    // Create a min-heap to store the end times of the meetings
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

    // Start with the first meeting and add its end time to the min-heap
    minHeap.push(meetings[0][1]);

    // Traverse the sorted meetings and update the min-heap accordingly
    for (int i = 1; i < meetings.size(); ++i) {
        if (meetings[i][0] >= minHeap.top()) {
            // The current meeting can reuse a room by popping the previous end time
            minHeap.pop();
        }
        // Add the current meeting's end time to the min-heap
        minHeap.push(meetings[i][1]);
    }

    // The size of the min-heap at the end will be the minimum number of meeting rooms required
    return minHeap.size();
}

int main() {
    std::vector<std::vector<int>> meetings = {{0, 30}, {5, 10}, {15, 20}};

    int result = minMeetingRooms(meetings);

    std::cout << "Minimum number of meeting rooms required: " << result << std::endl;

    return 0;
}

Explanation:

1. The minMeetingRooms function takes a reference to a vector of vectors meetings.
2. We sort the meetings vector based on their start time in ascending order using a custom comparator. This helps us find overlapping meetings efficiently.
3. We create a min-heap (priority queue) minHeap to store the end times of the meetings. The min-heap will ensure that the meeting with the earliest end time is always at the top.
4. We start with the first meeting and add its end time to the min-heap.
5. We then traverse the sorted meetings vector from the second meeting onwards. For each meeting, we check if its start time is greater than or equal to the end time of the meeting at the top of the min-heap. If this condition holds, it means the current meeting can reuse a room by replacing the previous meeting. In this case, we pop the previous meeting’s end time from the min-heap.
6. We always add the end time of the current meeting to the min-heap, whether it is a new meeting or a meeting that reused a room.
7. After processing all meetings, the size of the min-heap will be the minimum number of meeting rooms required to hold all meetings without any overlaps.

Time Complexity:

The time complexity of this solution is O(n log n), where n is the number of meetings in the input vector meetings. The main factors in the time complexity are the sorting step (O(n log n)) and the operations on the min-heap, which takes O(log n) time for each meeting.

Space Complexity:

The space complexity of this solution is O(n), where n is the number of meetings in the input vector meetings. This is because we use the min-heap to store the end times of the meetings, which has a maximum size of n.