Meeting Rooms III

Difficulty: Hard Source: NeetCode

Problem

You are given an integer n representing the number of rooms numbered 0 to n - 1. You are also given a 2D integer array meetings where meetings[i] = [start_i, end_i] represents the start and end times of meeting i (end time is exclusive — the room is free again at end_i).

All meetings must be held. Each meeting is assigned to the lowest-numbered available room. If no room is available, the meeting is delayed until the earliest room becomes free. The delayed meeting retains its original duration. Return the room number that held the most meetings. If multiple rooms held the same number, return the room with the lowest number.

Example 1: Input: n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]] Output: 0

Example 2: Input: n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]] Output: 1

Constraints:

• 1 <= n <= 100
• 1 <= meetings.length <= 10^5
• 0 <= start_i < end_i <= 5 * 10^5
• All values of start_i are unique.

Prerequisites

Before attempting this problem, you should be comfortable with:

• Min-heap (priority queue) — quickly finding the room that becomes free soonest and the lowest-numbered available room
• Sorting — processing meetings in chronological order
• Simulation — carefully tracking the state of each room at each step

1. Brute Force

Intuition

Sort meetings by start time and process them one by one. For each meeting, scan all rooms in order to find the lowest-numbered free one. If none is free, find which room ends soonest, delay the meeting to that time, and use that room. Simple but slow for large inputs.

Algorithm

1. Sort meetings by start time.
2. Maintain end_times[i] = when room i next becomes free (initially 0).
3. Maintain count[i] = meetings held in room i.
4. For each meeting [start, end]:
   • Find the lowest-indexed room r where end_times[r] <= start. If found, assign this meeting.
   • Otherwise, find the room r with the smallest end_times[r], delay the meeting: new end = end_times[r] + (end - start).
   • Update end_times[r] and count[r].
5. Return the room with the highest count (lowest index on ties).

Solution

def most_booked_brute(n, meetings):
    meetings.sort()
    end_times = [0] * n
    count = [0] * n

    for start, end in meetings:
        duration = end - start
        # Try to find the lowest-indexed free room
        assigned = -1
        for i in range(n):
            if end_times[i] <= start:
                assigned = i
                break

        if assigned == -1:
            # No room available — use the one that frees up soonest
            earliest_end = min(end_times)
            assigned = end_times.index(earliest_end)
            end_times[assigned] = earliest_end + duration
        else:
            end_times[assigned] = end

        count[assigned] += 1

    # Return room with most meetings (lowest index on tie)
    return count.index(max(count))


print(most_booked_brute(2, [[0,10],[1,5],[2,7],[3,4]]))        # 0
print(most_booked_brute(3, [[1,20],[2,10],[3,5],[4,9],[6,8]])) # 1

Complexity

• Time: O(m * n) — for each meeting, scan all n rooms
• Space: O(n)

2. Two Min-Heaps

Intuition

Use two heaps to track room state efficiently. One min-heap holds available room numbers (so the smallest is always at the top). Another min-heap holds occupied rooms as (end_time, room_number) pairs (so the earliest-freeing room is always at the top).

For each meeting in sorted order: first, pop all rooms from the occupied heap that have already ended and move them back to the available heap. Then, if the available heap is non-empty, grab the lowest-numbered room. If not, pop the earliest-ending room from the occupied heap, delay the meeting to start when that room is free, and reuse it. Push the room onto the occupied heap with its new end time.

Algorithm

1. Sort meetings by start time.
2. Initialize available = min-heap([0, 1, ..., n-1]) and occupied = min-heap() (pairs of (end_time, room_id)).
3. Initialize count = [0] * n.
4. For each meeting [start, end]:
   • Move rooms from occupied to available if their end time ≤ start.
   • If available is non-empty: pop the lowest-numbered room, schedule meeting ending at end.
   • Else: pop (earliest_end, room) from occupied, schedule ending at earliest_end + (end - start).
   • Push (new_end, room) onto occupied, increment count[room].
5. Return the room with the highest count (ties broken by lowest index).

Solution

import heapq

def most_booked(n, meetings):
    meetings.sort()
    available = list(range(n))  # min-heap of free room numbers
    heapq.heapify(available)
    occupied = []               # min-heap of (end_time, room_id)
    count = [0] * n

    for start, end in meetings:
        # Free rooms whose meetings have ended
        while occupied and occupied[0][0] <= start:
            end_time, room = heapq.heappop(occupied)
            heapq.heappush(available, room)

        if available:
            # Assign to lowest-numbered free room
            room = heapq.heappop(available)
            heapq.heappush(occupied, (end, room))
        else:
            # All rooms busy — wait for the earliest-ending one
            earliest_end, room = heapq.heappop(occupied)
            new_end = earliest_end + (end - start)
            heapq.heappush(occupied, (new_end, room))

        count[room] += 1

    # Room with most meetings; lowest index wins on tie
    max_count = max(count)
    return count.index(max_count)


print(most_booked(2, [[0,10],[1,5],[2,7],[3,4]]))        # 0
print(most_booked(3, [[1,20],[2,10],[3,5],[4,9],[6,8]])) # 1
print(most_booked(2, [[0,10],[1,5],[2,7],[3,4]]))        # 0

Complexity

• Time: O(m log m + m log n) — sorting meetings + heap operations per meeting
• Space: O(n + m) — two heaps

Common Pitfalls

Freeing rooms too eagerly. Only free a room when end_time <= start (the room is free by the time the meeting begins). Using strict < would incorrectly prevent a room from being reused when back-to-back scheduling is possible.

Forgetting to preserve original duration when delaying. A delayed meeting keeps its original length. If a meeting [3,7] (duration 4) is delayed until room frees at time 10, the new end is 10 + 4 = 14, not 10 + 7 = 17.

Not breaking ties correctly. When multiple rooms free up at the same time, the problem requires the lowest-numbered room. The tuple comparison (end_time, room_id) in the occupied heap handles this naturally — Python compares tuples lexicographically.