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 one meeting room:

• Room 1: [2,4] [7,10]

Steps

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

2. Use a min-heap (PriorityQueue): A min-heap will store the end times of meetings currently in progress. The heap's top element always represents the meeting that will end earliest.

3. 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 ending meeting (heap's top), it means we can reuse a room. Remove the top element from the heap and add the current interval's end time to the heap.
   • Otherwise, we need a new room. Add the current interval's end time to the heap.

4. Return the heap size: After processing all intervals, the size of the min-heap represents the minimum number of rooms needed.

Explanation

The algorithm leverages the fact that we can reuse a room if the current meeting's start time is after the earliest ending meeting. The min-heap efficiently tracks the earliest ending times, allowing us to make optimal room assignments. By always using the room that frees up earliest, we minimize the total number of rooms needed.

Code

import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return 0;
        }

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

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

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

            // If a meeting has ended before the current meeting starts, reuse the room
            if (!minHeap.isEmpty() && start >= minHeap.peek()) {
                minHeap.poll(); // Remove the earliest ending meeting
            }
            // Add the current meeting's end time to the heap
            minHeap.offer(end);
        }

        // Heap size represents the minimum number of rooms
        return minHeap.size();
    }
}

Complexity

• Time Complexity: O(N log N), dominated by the sorting of intervals. The heap operations (insertion and deletion) take logarithmic time.
• Space Complexity: O(N) in the worst case, where N is the number of intervals. The space is used by the min-heap, which can hold up to all the intervals' end times if all meetings overlap.