Meeting Rooms II - C++ Solution with O(n log n) Time Complexity

Given an array consisting of meeting time intervals, which are represented by the start and end times ([s0, e0], [s1, e1], ...], determine the minimum number of meeting rooms needed in order to be able to accommodate all meetings at every moment of time.

Example:

Input: [[5, 10], [0, 30], [15, 20]]
Output: 2
Explanation: 1st and 3rd meetings can be assigned to the first room
             2nd meeting can be assigned to room 2

Note:

You may assume the interval's end point is always greater than its start point.
Intervals like [1,2] and [2,3] have borders "touching" but they don't overlap.

Your algorithm should run in O(n log n) time and use O(n) extra space.

Understanding the Problem

The core challenge of this problem is to determine the minimum number of meeting rooms required to accommodate all meetings without any overlap. This problem is significant in scheduling and resource allocation scenarios, such as booking conference rooms or managing CPU tasks.

Potential pitfalls include misunderstanding the overlap conditions and not efficiently managing the intervals.

Approach

To solve this problem, we can use a greedy algorithm with a priority queue (min-heap). The idea is to keep track of the end times of meetings currently using a room. By sorting the intervals by their start times and using a min-heap to track the earliest ending meeting, we can efficiently determine the minimum number of rooms required.

Naive Solution

A naive solution would involve checking each meeting against all others to see if they overlap, which would result in a time complexity of O(n^2). This is not optimal for large inputs.

Optimized Solution

The optimized solution involves the following steps:

Sort the intervals by their start times.
Use a min-heap to keep track of the end times of meetings currently using a room.
Iterate through the sorted intervals and for each interval:
- If the room due to free up the earliest is free, remove it from the heap.
- Add the current meeting's end time to the heap.
- The size of the heap at any point will give the number of rooms required at that time.

Algorithm

Here is a step-by-step breakdown of the algorithm:

Sort the intervals by their start times.
Initialize a min-heap to keep track of end times.
Iterate through each interval:
- If the heap is not empty and the earliest end time is less than or equal to the current start time, remove the top of the heap.
- Add the current end time to the heap.
The size of the heap at the end of the iteration will be the minimum number of rooms required.

Code Implementation


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

using namespace std;

// Function to find the minimum number of meeting rooms required
int minMeetingRooms(vector<vector<int>>& intervals) {
    if (intervals.empty()) return 0;

    // Sort the 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 keep track of end times
    priority_queue<int, vector<int>, greater<int>> minHeap;

    // Add the end time of the first meeting
    minHeap.push(intervals[0][1]);

    for (int i = 1; i < intervals.size(); ++i) {
        // If the room due to free up the earliest is free, remove it from the heap
        if (intervals[i][0] >= minHeap.top()) {
            minHeap.pop();
        }
        // Add the current meeting's end time to the heap
        minHeap.push(intervals[i][1]);
    }

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

int main() {
    vector<vector<int>> intervals = {{5, 10}, {0, 30}, {15, 20}};
    cout << "Minimum number of meeting rooms required: " << minMeetingRooms(intervals) << endl;
    return 0;
}

Complexity Analysis

The time complexity of this solution is O(n log n) due to the sorting step and the operations on the min-heap. The space complexity is O(n) because we store all the end times in the heap.

Edge Cases

Potential edge cases include:

No meetings: The output should be 0.
Meetings that do not overlap: The output should be 1.
All meetings overlap: The output should be the number of meetings.

Testing

To test the solution comprehensively, consider the following test cases:

[[5, 10], [0, 30], [15, 20]] - Expected output: 2
[[1, 5], [6, 10], [11, 15]] - Expected output: 1
[[1, 10], [2, 6], [5, 8], [7, 12]] - Expected output: 3

Thinking and Problem-Solving Tips

When approaching such problems, it is crucial to:

Understand the problem constraints and requirements.
Think about edge cases and how to handle them.
Consider different data structures and algorithms that can optimize the solution.
Practice similar problems to improve problem-solving skills.

Conclusion

In this blog post, we discussed the problem of determining the minimum number of meeting rooms required to accommodate all meetings. We explored a naive solution and an optimized solution using a min-heap. We also provided a detailed explanation of the algorithm, code implementation, complexity analysis, and testing strategies. Understanding and solving such problems is crucial for improving algorithmic thinking and problem-solving skills.

Additional Resources

For further reading and practice, consider the following resources: