Meeting Rooms II

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 [[0, 30],[5, 10],[15, 20]], return 2.

Naive Solution

A naive solution would be to iterate through all the intervals and for each interval, check if it overlaps with any of the existing rooms. If it doesn't overlap, we can assign it to an existing room. If it overlaps with all existing rooms, we need to create a new room. This approach is inefficient because it requires comparing each interval with all existing rooms.

Optimal Solution

The optimal solution involves sorting the intervals by their start times and then using a min-heap to track the end times of the meetings in progress. The min-heap allows us to efficiently find the meeting that ends earliest.

Here's a step-by-step breakdown:

1. Sort the intervals: Sort the intervals by their start times. This ensures that we process meetings in the order they begin.
2. Initialize a min-heap: Create a min-heap (priority queue) to store the end times of the meetings currently in progress. The root of the heap will always be the meeting that ends earliest.
3. Iterate through the sorted intervals:
   • For each interval, check if the start time of the current meeting is greater than or equal to the earliest ending time in the min-heap (the root of the heap).
     • If it is, it means the earliest ending meeting has finished, and we can reuse that room. Remove the earliest ending time from the heap.
     • If it isn't, it means the current meeting overlaps with existing meetings, and we need a new room.
   • Add the end time of the current meeting to the min-heap.
4. The size of the min-heap at the end represents the minimum number of conference rooms required.

Edge Cases

• Empty input: If the input array is empty, return 0.
• Null input: Handle the case where the input array is null.
• Overlapping intervals: The algorithm correctly handles overlapping intervals.
• Non-overlapping intervals: The algorithm correctly handles non-overlapping intervals.
• Single interval: If there's only one interval, return 1.

Code

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

public class MeetingRoomsII {

    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 merged intervals
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

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

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

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

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

    public static void main(String[] args) {
        MeetingRoomsII meetingRooms = new MeetingRoomsII();

        // Example usage
        int[][] intervals1 = {{0, 30}, {5, 10}, {15, 20}};
        System.out.println("Minimum meeting rooms required: " + meetingRooms.minMeetingRooms(intervals1)); // Output: 2

        int[][] intervals2 = {{7,10},{2,4}};
         System.out.println("Minimum meeting rooms required: " + meetingRooms.minMeetingRooms(intervals2)); // Output: 1

        int[][] intervals3 = {{1,5},{8,9},{8,9}};
        System.out.println("Minimum meeting rooms required: " + meetingRooms.minMeetingRooms(intervals3)); // Output: 2
    }
}

Big O Runtime

• Sorting: O(n log n), where n is the number of intervals.
• Iterating through the intervals: O(n).
• Heap operations (add and poll): O(log n) for each operation, and we perform at most n operations. So it would be O(n log n).

Therefore, the overall time complexity is O(n log n).

Big O Space

• The space complexity is dominated by the min-heap, which can store at most n end times in the worst case. Therefore, the space complexity is O(n).