Meeting Rooms II in JavaScript (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 accounting for meetings that end exactly when another starts.

Approach

To solve this problem, we can use a greedy algorithm with a priority queue (min-heap). Here's a step-by-step approach:

Sort the meetings 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 meetings:
- If the room due to free the earliest is free before the next meeting starts, reuse that room (remove the top of the heap and add the new end time).
- If not, allocate a new room (add the new end time to the heap).
The size of the heap at the end will be the minimum number of rooms required.

Algorithm

Here's a detailed breakdown of the algorithm:

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

Code Implementation

/**
 * @param {number[][]} intervals
 * @return {number}
 */
function minMeetingRooms(intervals) {
    if (intervals.length === 0) {
        return 0;
    }

    // Sort the intervals by start time
    intervals.sort((a, b) => a[0] - b[0]);

    // Min-heap to track the end times of meetings
    const heap = [];

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

    for (let i = 1; i < intervals.length; i++) {
        // If the room due to free up the earliest is free, remove it from the heap
        if (heap[0] <= intervals[i][0]) {
            heap.shift();
        }

        // Add the current meeting's end time to the heap
        heap.push(intervals[i][1]);

        // Re-sort the heap
        heap.sort((a, b) => a - b);
    }

    // The size of the heap is the number of rooms required
    return heap.length;
}

// Example usage:
const intervals = [[5, 10], [0, 30], [15, 20]];
console.log(minMeetingRooms(intervals)); // Output: 2

Complexity Analysis

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

Edge Cases

Consider the following edge cases:

No meetings: The output should be 0.
Meetings that do not overlap: The output should be 1.
Meetings that start and end at the same time: The algorithm should handle this correctly.

Testing

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

// Test case 1: No meetings
console.log(minMeetingRooms([])); // Output: 0

// Test case 2: Meetings that do not overlap
console.log(minMeetingRooms([[1, 2], [3, 4], [5, 6]])); // Output: 1

// Test case 3: Meetings that overlap
console.log(minMeetingRooms([[1, 4], [2, 5], [7, 9]])); // Output: 2

// Test case 4: Meetings that start and end at the same time
console.log(minMeetingRooms([[1, 2], [2, 3], [3, 4]])); // Output: 1

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Break down the problem into smaller parts and solve each part step-by-step.
Think about edge cases and how your solution handles them.
Practice similar problems to improve your problem-solving skills.

Conclusion

In this blog post, we discussed how to determine the minimum number of meeting rooms required to accommodate all meetings using a greedy algorithm with a priority queue. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for efficient resource management and scheduling.

Additional Resources

For further reading and practice, consider the following resources: