Meeting Rooms II medium

Problem Statement

Given an array of meeting time intervals 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 since they do not overlap.

Steps

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

2. Use a min-heap: A min-heap (priority queue) will store the end times of the meetings currently in use. The heap's smallest element will represent the meeting that ends earliest.

3. Iterate through the sorted intervals: For each interval:

   • If the heap is empty or the current meeting's start time is greater than or equal to the earliest ending meeting (top of the heap), it means we can reuse a room. Pop the earliest ending meeting from the heap and push the current meeting's end time onto the heap.
   • Otherwise, we need a new room. Push the current meeting's end time onto 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's core idea is to greedily assign meetings to existing rooms whenever possible. By sorting the intervals by start time, we ensure that we consider meetings in chronological order. The min-heap keeps track of the earliest available room (represented by the earliest ending meeting). If a new meeting's start time is after the earliest ending meeting, we reuse that room; otherwise, we require a new room. This strategy minimizes the total number of rooms used.

Code

import heapq

def minMeetingRooms(intervals):
    """
    Finds the minimum number of meeting rooms required.

    Args:
        intervals: A list of meeting time intervals, where each interval is a list [start, end].

    Returns:
        The minimum number of meeting rooms required.
    """
    # Sort intervals by start time
    intervals.sort()

    # Min-heap to store end times of ongoing meetings
    heap = []

    for interval in intervals:
        start, end = interval
        
        #If heap is not empty and current meeting starts after the earliest ending meeting
        if heap and start >= heap[0]:
            #Reuse a room: replace the earliest end time with the current meeting's end time
            heapq.heapreplace(heap, end)
        else:
            #Need a new room
            heapq.heappush(heap, end)

    return len(heap)

Complexity

• Time Complexity: O(N log N), dominated by the sorting of intervals. Heap operations take O(log N) time each.
• Space Complexity: O(N) in the worst case, to store the min-heap (if all meetings need separate rooms).