Meeting Rooms II medium

Problem Statement

Given an array of meeting time 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], [15,20]

Example 2

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

Steps

1. Sort Intervals: Sort the intervals based on their start times. This allows us to process meetings in chronological order.

2. Min-Heap: Use a min-heap (priority queue) to track the end times of the currently occupied meeting rooms. The min-heap will always store the earliest ending meeting time at the top.

3. Iterate and Manage Rooms: Iterate through the sorted intervals. For each interval:

   • If the heap is empty or the current interval's start time is greater than or equal to the earliest end time (heap's top), it means we can reuse a room. Remove the earliest end time from the heap and add the current interval's end time.
   • Otherwise, we need a new room. Add the current interval's end time to the heap.

4. Result: The final size of the min-heap represents the minimum number of meeting rooms required.

Explanation

The algorithm works because it efficiently manages the allocation of rooms. Sorting ensures that we consider meetings in the order they occur. The min-heap helps to identify the room that will be available earliest, minimizing the total number of rooms needed. If a new meeting's start time is after the earliest ending meeting, it can reuse that room; otherwise, a new room is needed.

Code (C#)

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public int MinMeetingRooms(int[][] intervals) {
        if (intervals == null || intervals.Length == 0) return 0;

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

        // Min-heap to store end times of ongoing meetings
        PriorityQueue<int, int> minHeap = new PriorityQueue<int, int>();

        // Iterate through intervals
        foreach (int[] interval in intervals) {
            int start = interval[0];
            int end = interval[1];

            // Remove meetings that have ended
            while (minHeap.Count > 0 && minHeap.Peek() <= start) {
                minHeap.Dequeue();
            }

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

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

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. In the best case, space complexity is O(1).