Meeting Rooms II Solution

Problem Description

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

For example, given the intervals [[0, 30],[5, 10],[15, 20]], the output should be 2.

Naive Solution

A brute-force solution would involve checking each interval against all other intervals to see if they overlap. For each interval, we'd count how many other intervals overlap with it. The maximum number of overlaps any interval has would be the minimum number of meeting rooms required.

This approach is inefficient because, for each interval, we iterate through the entire list of intervals.

Big O Runtime

O(n^2), where n is the number of intervals, due to the nested loops used to compare each interval with every other interval.

Big O Space

O(1), as we only use a constant amount of extra space.

Optimal Solution

The optimal solution involves sorting the intervals based on their start times. Then, we use a min-heap to track the end times of the meetings currently in progress. We iterate through the sorted intervals. For each interval, we check if the meeting room freed up. if it is freed up we remove the meeting end time from the heap. We keep a counter for tracking the maximum number of meeting rooms required.

1. Sort the intervals: Sort the input array of intervals by their start times.
2. Min-Heap: Use a min-heap (priority queue) to store the end times of ongoing meetings.
3. Iterate and Check: Iterate through the sorted intervals. For each interval:
   • If the current interval's start time is greater than or equal to the smallest end time in the min-heap (meaning a meeting room is available), remove the smallest end time from the min-heap.
   • Add the current interval's end time to the min-heap.
4. Result: The size of the min-heap at any point represents the number of overlapping meetings, which is the number of meeting rooms needed.

Edge Cases

• Empty input: If the input array is empty, return 0.
• Null input: If the input array is null, handle the null pointer exception or return 0, depending on the requirements.
• Overlapping intervals: The core logic handles overlapping intervals correctly.
• Non-overlapping intervals: The algorithm correctly identifies when rooms can be reused.
• Single interval: If there's only one interval, only one room is needed.

Big O Runtime

O(n log n), where n is the number of intervals. Sorting the intervals takes O(n log n) time, and iterating through the intervals and performing heap operations (insertion and deletion) takes O(n log n) time in the worst case.

Big O Space

O(n), where n is the number of intervals. This is because, in the worst-case scenario (when all meetings overlap), the min-heap can contain all the end times of the intervals.

Code (Java)

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

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

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

        // Use a min-heap to track the end times of meetings
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // Add the first meeting to the heap
        minHeap.add(intervals[0][1]);

        // Iterate through the rest of the meetings
        for (int i = 1; i < intervals.length; i++) {
            // If the current meeting starts after the last meeting ends,
            // then we can reuse the room
            if (intervals[i][0] >= minHeap.peek()) {
                minHeap.poll();
            }

            // Add the current meeting to the heap
            minHeap.add(intervals[i][1]);
        }

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