Description

Given an array of meeting time intervals intervals where intervals[i] = [start_i, end_i], return the minimum number of conference rooms required.

給定一個會議時間間隔的陣列 intervals，其中 intervals[i] = [start_i, end_i]，返回所需的最小會議室數量。

Example 1

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2

Example 2

Input: intervals = [[7,10],[2,4]]
Output: 1

Constraints:

Solution

function minMeetingRooms(intervals: number[][]): number {
    if (intervals.length === 0) {
        return 0;
    }

    // 1. Sort intervals by their start time (O(n log n))
    intervals.sort((a, b) => a[0] - b[0]);

    // 2. Initialize a min-heap (as an array)
    const minHeap: number[] = [];

    // Helper functions to manage the min-heap
    const addMeeting = (heap: number[], end: number) => {
        heap.push(end);
        heap.sort((a, b) => a - b); // Ensure the heap is sorted after adding an element
    };

    const removeEarliestMeeting = (heap: number[]) => {
        heap.shift(); // Remove the earliest ending meeting
    };

    // 3. Iterate through sorted intervals (O(n))
    for (const [start, end] of intervals) {
        // If the room with the earliest end time is free, remove it from the heap
        if (minHeap.length > 0 && minHeap[0] <= start) {
            minHeap.shift()
        }

        // Add the current meeting's end time to the heap
        addMeeting(minHeap, end);
    }

    // 4. The size of the heap is the maximum number of occupied rooms at any time
    return minHeap.length;
}

// Example usage
const intervals1 = [[0, 30], [5, 10], [15, 20]];
const minRooms1 = minMeetingRooms(intervals1);
console.log("Minimum meeting rooms required:", minRooms1); // Output: 2

const intervals2 = [[7, 10], [2, 4]];
const minRooms2 = minMeetingRooms(intervals2);
console.log("Minimum meeting rooms required:", minRooms2); // Output: 1

Complexity