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. We need two rooms as the first and second meetings overlap. The first meeting takes room one. Then, the second meeting from 5 to 10 needs a second room because room one is occupied from 0 to 30. The third meeting can use room one.

Naive Solution

A brute force solution would involve checking each meeting interval against all other meeting intervals to find overlaps. For each meeting, we'd iterate through the existing rooms (represented by a list of meeting intervals) and see if the current meeting overlaps with any of the meetings in those rooms. If it doesn't overlap with any, we create a new room and add the meeting to it. If it overlaps with one or more existing rooms, we pick a room that is available.

This approach has a time complexity of O(n^2) where n is the number of meeting intervals, due to the nested loops required to compare each meeting with every other meeting.

Edge Cases:

• Empty input: If the input list is empty, we need 0 rooms.
• Single meeting: If there's only one meeting, we need 1 room.
• Meetings sorted by start time or end time could affect the traversal and comparison process.

Optimal Solution

The optimal solution uses sorting and a min-heap (priority queue). We sort the meeting intervals by start time. Then, we iterate through the sorted intervals, using a min-heap to keep track of the end times of meetings that are currently in rooms.

For each meeting, we check if the earliest ending meeting in the min-heap has ended before the current meeting starts. If it has, we can reuse that room (pop the min-heap). Otherwise, we need a new room (add the current meeting's end time to the min-heap).

Algorithm:

1. Sort the intervals by start time.
2. Initialize a min-heap to store end times.
3. Iterate through the sorted intervals.
   • If the min-heap is not empty and the current meeting's start time is greater than or equal to the earliest ending time in the min-heap, remove the earliest ending time.
   • Add the current meeting's end time to the min-heap.
4. The size of the min-heap at the end is the minimum number of rooms needed.

Code:

import heapq

def minMeetingRooms(intervals):
    if not intervals:
        return 0

    # Sort by start time
    intervals.sort(key=lambda x: x[0])

    # Use a min-heap to track the end times of meetings that are currently in rooms.
    rooms = []

    # Iterate through the meetings.
    for interval in intervals:
        # If the current meeting starts after the meeting on the top of the heap ends,
        # remove the meeting from the heap.
        if rooms and interval[0] >= rooms[0]:
            heapq.heappop(rooms)

        # Add the end time of the current meeting to the heap.
        heapq.heappush(rooms, interval[1])

    # The size of the heap is the number of rooms required.
    return len(rooms)

Example:

intervals = [[0, 30],[5, 10],[15, 20]]
print(minMeetingRooms(intervals)) # Output: 2

Time Complexity:

• Sorting the intervals takes O(n log n) time.
• Iterating through the intervals takes O(n) time.
• Heap operations (push and pop) take O(log n) time each, and we perform at most n such operations.

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

Space Complexity:

• We use a min-heap to store the end times of meetings. In the worst case, all meetings overlap, and the heap will contain n end times.

Therefore, the space complexity is O(n).