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] and [15,20]

Example 2

Input: intervals = [[7,10],[2,4]] Output: 1 Explanation: We can use the same meeting room for both intervals.

Steps

1. Sort Intervals: Sort the intervals based on their start times. This helps in efficiently processing the meetings.

2. Min-Heap: Use a min-heap data structure (priority queue) to store the end times of the ongoing meetings. The min-heap will always keep track of the meeting with the earliest end time at the top.

3. Iterate and Manage Meetings: Iterate through the sorted intervals:

   • If the current meeting's start time is greater than or equal to the earliest end time (top of the heap), it means we can reuse a room. Pop the earliest end time from the heap and push the current meeting's end time.
   • Otherwise, we need a new room. Push the current meeting's end time onto the heap.

4. Result: The size of the min-heap at the end of the iteration represents the minimum number of rooms required.

Explanation

The algorithm leverages the fact that we only need a new room when a meeting starts before any of the ongoing meetings end. Sorting ensures we consider meetings in chronological order. The min-heap efficiently tracks the earliest ending meeting, allowing us to reuse rooms whenever possible.

Code (TypeScript)

import { MinPriorityQueue } from '@datastructures-js/priority-queue';

function minMeetingRooms(intervals: number[][]): number {
    // Sort intervals by start time
    intervals.sort((a, b) => a[0] - b[0]);

    // Min-heap to store end times of ongoing meetings
    const minHeap = new MinPriorityQueue({ priority: (x) => x });

    for (const [start, end] of intervals) {
        // If current meeting starts after the earliest ending meeting, reuse a room
        if (minHeap.size() > 0 && start >= minHeap.front().element) {
            minHeap.dequeue();
        }
        // Add the current meeting's end time to the heap
        minHeap.enqueue(end);
    }

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

Complexity

• Time Complexity: O(N log N), dominated by the sorting of intervals. The heap operations (enqueue and dequeue) take O(log N) time each.
• Space Complexity: O(N) in the worst case, to store the end times in the min-heap. If all meetings overlap, the heap will contain all meeting end times. The sorting process might use extra space depending on the implementation.

Note: This solution uses the @datastructures-js/priority-queue package for the min-heap. You'll need to install it using: npm install @datastructures-js/priority-queue or yarn add @datastructures-js/priority-queue. You could also implement a min-heap from scratch, but using a library simplifies the code.