Problem Statement

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required to hold all the meetings without any overlaps.

Note that meetings ending and starting at the exact same time (e.g., [1, 2] and [2, 3]) are not considered overlapping and can share the exact same conference room.

Additional information

• 1 <= intervals.length <= 10^4
• 0 <= starti < endi <= 10^6

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]]

Output: 2

Explanation: - Room 1: [0,30]

• Room 2: [5,10] and [15,20]
  Since the meeting [0,30] spans across the duration of both other meetings, we need at least 2 conference rooms.

Example 2:

Input: intervals = [[7,10],[2,4]]

Output: 1

Explanation: The meetings do not overlap at all, so they can be held sequentially in a single conference room.

Min-Heap (Priority Queue)

Intuition

When manually allocating conference rooms, we naturally process meetings in chronological order based on when they start. As a new meeting is about to begin, we check if any of our currently occupied rooms have freed up.

We can simulate this process using a Min-Heap (Priority Queue). First, we sort the meetings by their start times. We use the Min-Heap to store the end times of all meetings that are currently occupying a room.

Because it's a Min-Heap, the room that frees up the earliest will always be sitting at the very top. When examining a new meeting, we compare its start time to the top of the heap. If the new meeting starts after or at the exact same time the earliest meeting finishes, we can safely reuse that room (by popping the old end time from the heap and pushing the new end time). If the new meeting starts before the earliest room frees up, we have no choice but to allocate a brand new room (by pushing the new end time to the heap without popping).

The size of the heap at the very end represents the total number of unique rooms we had to allocate!

Algorithm

1. If the intervals array is empty, return 0.
2. Sort the intervals array based on the start time (index 0).
3. Initialize a min_heap and push the end time of the very first meeting: intervals[0][1].
4. Iterate through the remaining meetings starting from index 1:

• If the current meeting's start time is greater than or equal to the top of the heap (min_heap[0] <= interval[0]), a room has freed up! Pop the top element from the heap.
• Push the current meeting's end time onto the heap (representing the room being occupied by the new meeting).

5. Return the length of the min_heap.

def min_meeting_rooms(intervals: list[list[int]]) -> int:
    if not intervals:
        return 0
        
    # Sort meetings chronologically by start time
    intervals.sort(key=lambda x: x[0])
    
    # The heap will store the end times of active meetings
    min_heap = []
    heapq.heappush(min_heap, intervals[0][1])
    
    for i in range(1, len(intervals)):
        # If the earliest ending meeting finishes before the current one starts, reuse the room
        if min_heap[0] <= intervals[i][0]:
            heapq.heappop(min_heap)
            
        # Allocate the room (either reused or brand new) to the current meeting
        heapq.heappush(min_heap, intervals[i][1])
        
    # The number of actively tracked end times equals the rooms required
    return len(min_heap)

Time & Space Complexity

• Time complexity: O(N log N)

• Reason: Sorting the intervals takes O(N log N) time. In the worst case (where every meeting overlaps), we push N elements onto the heap, which also takes O(N log N) time.

• Space complexity: O(N)

• Reason: The min_heap will store up to N elements if all meetings overlap simultaneously.

Chronological Ordering (Two Pointers) - Optimal

Intuition

There is an even more elegant way to solve this by entirely disassociating the start times from the end times.

We don't actually care which specific meeting ends when; we only care that some meeting has ended, effectively freeing up a room. We can extract all the start times into one array and all the end times into another array, and sort them completely independently!

Using two pointers, we simulate walking through time. If we encounter a start time, a meeting is beginning, so we increment our active_rooms counter. If we encounter an end time, a meeting has finished, so we decrement our active_rooms counter. We track the maximum number of active rooms we ever reach at any given point during this chronological sweep.

Algorithm

1. Extract all start times into a list start_times and all end times into a list end_times.
2. Sort both start_times and end_times in ascending order.
3. Initialize two pointers: s = 0 (for starts) and e = 0 (for ends).
4. Initialize active_rooms = 0 and max_rooms = 0.
5. While the s pointer is less than the length of the intervals:

• If start_times[s] < end_times[e], a new meeting has started before the earliest end time. We need a room.

• Increment active_rooms by 1.

• Advance the s pointer.

• Else (meaning start_times[s] >= end_times[e]), a meeting has ended, freeing up a room.

• Decrement active_rooms by 1.

• Advance the e pointer.

• Update max_rooms to be the maximum of its current value and active_rooms.

6. Return max_rooms.

def min_meeting_rooms(intervals: list[list[int]]) -> int:
    if not intervals:
        return 0
        
    start_times = sorted([i[0] for i in intervals])
    end_times = sorted([i[1] for i in intervals])
    
    s_ptr = 0
    e_ptr = 0
    active_rooms = 0
    max_rooms = 0
    
    while s_ptr < len(intervals):
        # A meeting starts before the next scheduled meeting ends
        if start_times[s_ptr] < end_times[e_ptr]:
            active_rooms += 1
            s_ptr += 1
        # A meeting has finished, freeing up a room
        else:
            active_rooms -= 1
            e_ptr += 1
            
        max_rooms = max(max_rooms, active_rooms)
            
    return max_rooms

Time & Space Complexity

• Time complexity: O(N log N)

• Reason: Extracting the times takes O(N) and sorting both lists takes O(N log N) time. The two-pointer sweep processes every start and end time exactly once, taking O(N) time. The sorting dominates the overall time complexity.

• Space complexity: O(N)

• Reason: We create two new lists (start_times and end_times), each of size N, to sort the times independently.