Meeting Rooms III

Description

You are given an integer n representing n meeting rooms numbered from 0 to n - 1.

You are also given a 2D integer array meetings where meetings[i] = [startᵢ, endᵢ] indicates that a meeting will be held during the half-closed time interval [startᵢ, endᵢ). All the values of startᵢ are unique.

Meetings are allocated to rooms according to these rules:

Lowest available room first: Each meeting is assigned to the unused room with the smallest room number.
Delay if no rooms available: If all rooms are occupied, the meeting is delayed until a room becomes free. The delayed meeting retains its original duration — only its start and end times shift forward.
Earlier original start time has priority: When a room becomes free and multiple meetings are waiting, the meeting with the earliest original start time gets the room first.

Return the number of the room that held the most meetings. If there is a tie, return the room with the lowest number.

Examples

Example 1

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

Output: 0

Explanation:

Time 0: Both rooms are free. Meeting [0,10] starts in room 0 (lowest available).
Time 1: Only room 1 is free. Meeting [1,5] starts in room 1.
Time 2: Both rooms are busy (room 0 until time 10, room 1 until time 5). Meeting [2,7] is delayed.
Time 3: Both rooms still busy. Meeting [3,4] is also delayed.
Time 5: Room 1 finishes. Meeting [2,7] (earlier original start) gets room 1. Duration was 5, so it runs [5,10).
Time 10: Both rooms finish. Meeting [3,4] gets room 0 (lowest available). Duration was 1, so it runs [10,11).

Room 0 held 2 meetings, room 1 held 2 meetings. Tie → return room 0 (lowest number).

Example 2

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

Output: 1

Explanation:

Time 1: All three rooms free. Meeting [1,20] → room 0.
Time 2: Rooms 1 and 2 free. Meeting [2,10] → room 1.
Time 3: Only room 2 free. Meeting [3,5] → room 2.
Time 4: All rooms busy. Meeting [4,9] delayed.
Time 5: Room 2 finishes. Meeting [4,9] gets room 2, duration 5, runs [5,10).
Time 6: All rooms busy. Meeting [6,8] delayed.
Time 10: Rooms 1 and 2 finish. Meeting [6,8] gets room 1 (lowest), duration 2, runs [10,12).

Room 0: 1 meeting, Room 1: 2 meetings, Room 2: 2 meetings. Max is 2. Tie between rooms 1 and 2 → return room 1 (lowest).

Constraints

1 ≤ n ≤ 100
1 ≤ meetings.length ≤ 10^5
meetings[i].length == 2
0 ≤ startᵢ < endᵢ ≤ 5 × 10^5
All values of startᵢ are unique

Editorial

Brute Force

Intuition

The most natural approach is to directly simulate the meeting allocation process. We maintain an array that tracks when each room becomes free (its "end time"). For each meeting, we scan through all rooms to find which ones are available.

Think of it like being a receptionist with a whiteboard showing when each room's current booking ends. When a new meeting request comes in:

First, sort all meetings by start time so we process them in chronological order.
For each meeting, scan the whiteboard looking for rooms where the end time ≤ the meeting's start time. Among all free rooms, pick the one with the smallest number.
If no rooms are free, find the room that becomes available earliest (smallest end time). The meeting is delayed to start when that room opens up, keeping its original duration.
Update the room's end time and increment its meeting counter.

This works correctly but involves scanning all n rooms for every meeting, which can be slow when both n and the number of meetings are large.

Step-by-Step Explanation

Let's trace through with n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]:

After sorting by start time: [[0,10],[1,5],[2,7],[3,4]] (already sorted).

Initialize: room_end = [0, 0], count = [0, 0]

Step 1: Meeting [0, 10]. Scan rooms:

Room 0: end_time=0 ≤ start=0? YES → room 0 is free.
Room 0 is the lowest free room. Assign meeting here.
room_end = [10, 0], count = [1, 0]

Step 2: Meeting [1, 5]. Scan rooms:

Room 0: end_time=10 ≤ start=1? NO → room 0 is busy.
Room 1: end_time=0 ≤ start=1? YES → room 1 is free.
Assign to room 1.
room_end = [10, 5], count = [1, 1]

Step 3: Meeting [2, 7] (duration = 5). Scan rooms:

Room 0: end_time=10 ≤ start=2? NO.
Room 1: end_time=5 ≤ start=2? NO.
No free rooms! Find room with earliest end time.
Room 0 ends at 10, Room 1 ends at 5. Room 1 is earliest.
Delay meeting to start at time 5. New end = 5 + (7-2) = 10.
room_end = [10, 10], count = [1, 2]

Step 4: Meeting [3, 4] (duration = 1). Scan rooms:

Room 0: end_time=10 ≤ start=3? NO.
Room 1: end_time=10 ≤ start=3? NO.
No free rooms! Find earliest end.
Room 0 ends at 10, Room 1 ends at 10. Tie → pick room 0 (lowest number).
Delay meeting to start at time 10. New end = 10 + (4-3) = 11.
room_end = [11, 10], count = [2, 2]

Result: count = [2, 2]. Max is 2. Tie → return room 0.

Brute Force — Direct Room Scanning Simulation — Watch how we scan all rooms for each meeting to find the lowest available room, or the room that becomes free earliest when all are busy.

Algorithm

Sort meetings by start time.
Initialize an array room_end of size n (all zeros — every room is free at time 0) and a count array of size n (all zeros).
For each meeting [start, end]:
a. Scan rooms 0 to n-1. Collect all rooms where room_end[j] ≤ start (free rooms).
b. If any free rooms exist, pick the one with the smallest index.
c. If no free rooms, find the room j with the smallest room_end[j] (ties broken by smallest j). The meeting is delayed: actual start becomes room_end[j], actual end becomes room_end[j] + (end - start).
d. Update room_end[j] and increment count[j].
Return the index with the highest count (smallest index for ties).

Code

class Solution {
public:
    int mostBooked(int n, vector<vector<int>>& meetings) {
        sort(meetings.begin(), meetings.end());
        vector<long long> roomEnd(n, 0);
        vector<int> count(n, 0);
        
        for (auto& m : meetings) {
            long long start = m[0], end = m[1];
            long long duration = end - start;
            
            // Find the lowest available room
            int bestRoom = -1;
            for (int j = 0; j < n; j++) {
                if (roomEnd[j] <= start) {
                    bestRoom = j;
                    break;
                }
            }
            
            if (bestRoom == -1) {
                // No free room — find the one that becomes free earliest
                long long earliest = LLONG_MAX;
                for (int j = 0; j < n; j++) {
                    if (roomEnd[j] < earliest) {
                        earliest = roomEnd[j];
                        bestRoom = j;
                    }
                }
                // Delay the meeting
                roomEnd[bestRoom] = earliest + duration;
            } else {
                roomEnd[bestRoom] = end;
            }
            count[bestRoom]++;
        }
        
        int result = 0;
        for (int i = 1; i < n; i++) {
            if (count[i] > count[result]) {
                result = i;
            }
        }
        return result;
    }
};

class Solution:
    def mostBooked(self, n: int, meetings: list[list[int]]) -> int:
        meetings.sort()
        room_end = [0] * n
        count = [0] * n
        
        for start, end in meetings:
            duration = end - start
            
            # Find the lowest available room
            best_room = -1
            for j in range(n):
                if room_end[j] <= start:
                    best_room = j
                    break
            
            if best_room == -1:
                # No free room — find earliest finishing room
                earliest = float('inf')
                for j in range(n):
                    if room_end[j] < earliest:
                        earliest = room_end[j]
                        best_room = j
                # Delay the meeting
                room_end[best_room] = earliest + duration
            else:
                room_end[best_room] = end
            
            count[best_room] += 1
        
        return count.index(max(count))

class Solution {
    public int mostBooked(int n, int[][] meetings) {
        Arrays.sort(meetings, (a, b) -> a[0] - b[0]);
        long[] roomEnd = new long[n];
        int[] count = new int[n];
        
        for (int[] m : meetings) {
            long start = m[0], end = m[1];
            long duration = end - start;
            
            // Find the lowest available room
            int bestRoom = -1;
            for (int j = 0; j < n; j++) {
                if (roomEnd[j] <= start) {
                    bestRoom = j;
                    break;
                }
            }
            
            if (bestRoom == -1) {
                // No free room — find earliest finishing room
                long earliest = Long.MAX_VALUE;
                for (int j = 0; j < n; j++) {
                    if (roomEnd[j] < earliest) {
                        earliest = roomEnd[j];
                        bestRoom = j;
                    }
                }
                // Delay the meeting
                roomEnd[bestRoom] = earliest + duration;
            } else {
                roomEnd[bestRoom] = end;
            }
            count[bestRoom]++;
        }
        
        int result = 0;
        for (int i = 1; i < n; i++) {
            if (count[i] > count[result]) {
                result = i;
            }
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(m × n + m log m)

Sorting the meetings takes O(m log m) where m is the number of meetings. For each of the m meetings, we scan up to n rooms to find an available room (or the earliest-finishing room). This gives O(m × n) for the simulation, making the total O(m × n + m log m). Since n can be up to 100 and m up to 10^5, this is up to 10^7 operations — acceptable but not optimal.

Space Complexity: O(n)

We use two arrays of size n: one for room end times and one for meeting counts. The sorting may use O(log m) additional space.

Why This Approach Is Not Efficient

The brute force scans all n rooms for every meeting, performing two tasks:

Finding the lowest-numbered free room (linear scan)
Finding the room with the earliest end time (another linear scan)

Both of these operations can be done much faster with the right data structures. A min-heap (priority queue) can find the minimum in O(log n) time instead of O(n).

The key insight: we need two separate min-heaps:

A free-rooms heap ordered by room number — instantly gives us the lowest available room.
A busy-rooms heap ordered by end time (with room number as tiebreaker) — instantly tells us which room finishes first.

When a meeting arrives, we first transfer all rooms whose end times have passed from the busy heap to the free heap. Then we either take the smallest room from the free heap, or pop the earliest-finishing room from the busy heap if all are occupied. This reduces each meeting's processing from O(n) to O(log n).

Optimal Approach - Two Min-Heaps

Intuition

Imagine managing a hotel front desk with n rooms. You have two lists:

Available rooms list (sorted by room number) — when a guest arrives, you glance at this list and immediately see the lowest-numbered available room.
Occupied rooms list (sorted by checkout time) — you can instantly see which room will be vacated next.

When a guest arrives:

First, check if any rooms have been vacated since the last guest arrived. Move those from the "occupied" list back to the "available" list.
If rooms are available, assign the one with the smallest number.
If all rooms are busy, look at the "occupied" list to see which room frees up first. Tell the guest to wait until then.

This is exactly what two min-heaps give us:

A free-rooms min-heap keyed by room index → O(log n) to get the lowest-numbered free room.
A busy-rooms min-heap keyed by (end_time, room_index) → O(log n) to get the room that finishes earliest.

We also maintain a count array to track how many meetings each room hosts. After processing all meetings, the room with the highest count (smallest index for ties) is our answer.

Step-by-Step Explanation

Let's trace through with n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]:

Initialize: free_heap = [0, 1], busy_heap = [], count = [0, 0]

Step 1: Meeting [0, 10], start=0.

Free up rooms: check busy_heap — it's empty. No rooms to free.
Free rooms available? YES (free_heap has [0, 1]).
Pop smallest from free_heap → room 0.
Push (end=10, room=0) into busy_heap.
count[0]++.
State: free=[1], busy=[(10,0)], count=[1,0]

Step 2: Meeting [1, 5], start=1.

Free up rooms: busy_heap top is (10, 0). 10 ≤ 1? NO. Nothing freed.
Free rooms available? YES (free_heap has [1]).
Pop smallest → room 1.
Push (5, 1) into busy_heap.
count[1]++.
State: free=[], busy=[(5,1),(10,0)], count=[1,1]

Step 3: Meeting [2, 7], start=2, duration=5.

Free up rooms: busy_heap top is (5, 1). 5 ≤ 2? NO. Nothing freed.
Free rooms available? NO (free_heap is empty).
Pop earliest from busy_heap → (5, room 1). Meeting delayed to start at time 5.
New end = 5 + (7-2) = 10. Push (10, 1) back.
count[1]++.
State: free=[], busy=[(10,0),(10,1)], count=[1,2]

Step 4: Meeting [3, 4], start=3, duration=1.

Free up rooms: busy_heap top is (10, 0). 10 ≤ 3? NO. Nothing freed.
Free rooms available? NO.
Pop earliest from busy_heap → (10, room 0). Tie broken by room index: room 0 comes first.
Meeting delayed to start at 10. New end = 10 + (4-3) = 11. Push (11, 0).
count[0]++.
State: free=[], busy=[(10,1),(11,0)], count=[2,2]

Result: count = [2, 2]. Max = 2, tie → return room 0.

Two Min-Heaps — Efficient Room Allocation — Watch how two heaps efficiently manage free and busy rooms. The free-heap gives the lowest-numbered available room in O(log n), and the busy-heap reveals the earliest-finishing room.

Algorithm

Sort meetings by start time.
Initialize:
- free_heap: min-heap containing [0, 1, ..., n-1] (all rooms available).
- busy_heap: empty min-heap, will store (end_time, room_index) pairs.
- count: array of n zeros.
For each meeting [start, end]:
a. Free up rooms: While busy_heap is non-empty AND top element's end_time ≤ start:
- Pop (end_time, room) from busy_heap.
- Push room into free_heap.
  b. Assign room:
- If free_heap is non-empty: pop room from free_heap (lowest number). Set actual_end = end.
- Else: pop (earliest_end, room) from busy_heap. Meeting delayed: actual_end = earliest_end + (end - start).
  c. Push (actual_end, room) into busy_heap. Increment count[room].
Return the index with the highest count (smallest index for ties).

Code

class Solution {
public:
    int mostBooked(int n, vector<vector<int>>& meetings) {
        sort(meetings.begin(), meetings.end());
        
        // Min-heap of available rooms (by room index)
        priority_queue<int, vector<int>, greater<int>> freeHeap;
        for (int i = 0; i < n; i++) freeHeap.push(i);
        
        // Min-heap of busy rooms: (end_time, room_index)
        priority_queue<pair<long long, int>,
                       vector<pair<long long, int>>,
                       greater<pair<long long, int>>> busyHeap;
        
        vector<int> count(n, 0);
        
        for (auto& m : meetings) {
            long long start = m[0], end = m[1];
            
            // Free up rooms that have finished
            while (!busyHeap.empty()
                   && busyHeap.top().first <= start) {
                freeHeap.push(busyHeap.top().second);
                busyHeap.pop();
            }
            
            if (!freeHeap.empty()) {
                // Assign to lowest-numbered free room
                int room = freeHeap.top();
                freeHeap.pop();
                count[room]++;
                busyHeap.push({end, room});
            } else {
                // Delay: wait for earliest room
                auto [earliest, room] = busyHeap.top();
                busyHeap.pop();
                count[room]++;
                busyHeap.push(
                    {earliest + (end - start), room});
            }
        }
        
        return max_element(count.begin(), count.end())
               - count.begin();
    }
};

import heapq

class Solution:
    def mostBooked(self, n: int, meetings: list[list[int]]) -> int:
        meetings.sort()
        
        # Min-heap of available rooms (by room index)
        free_heap = list(range(n))
        heapq.heapify(free_heap)
        
        # Min-heap of busy rooms: (end_time, room_index)
        busy_heap = []
        
        count = [0] * n
        
        for start, end in meetings:
            # Free up rooms that have finished
            while busy_heap and busy_heap[0][0] <= start:
                _, room = heapq.heappop(busy_heap)
                heapq.heappush(free_heap, room)
            
            if free_heap:
                # Assign to lowest-numbered free room
                room = heapq.heappop(free_heap)
                count[room] += 1
                heapq.heappush(busy_heap, (end, room))
            else:
                # Delay: wait for earliest room
                earliest, room = heapq.heappop(busy_heap)
                count[room] += 1
                heapq.heappush(
                    busy_heap,
                    (earliest + (end - start), room)
                )
        
        return count.index(max(count))

class Solution {
    public int mostBooked(int n, int[][] meetings) {
        Arrays.sort(meetings, (a, b) -> a[0] - b[0]);
        
        // Min-heap of available rooms (by room index)
        PriorityQueue<Integer> freeHeap =
            new PriorityQueue<>();
        for (int i = 0; i < n; i++) freeHeap.add(i);
        
        // Min-heap of busy rooms: [end_time, room_index]
        PriorityQueue<long[]> busyHeap =
            new PriorityQueue<>((a, b) ->
                a[0] != b[0]
                    ? Long.compare(a[0], b[0])
                    : Long.compare(a[1], b[1]));
        
        int[] count = new int[n];
        
        for (int[] m : meetings) {
            long start = m[0], end = m[1];
            
            // Free up rooms that have finished
            while (!busyHeap.isEmpty()
                   && busyHeap.peek()[0] <= start) {
                freeHeap.add((int) busyHeap.poll()[1]);
            }
            
            if (!freeHeap.isEmpty()) {
                int room = freeHeap.poll();
                count[room]++;
                busyHeap.add(new long[]{end, room});
            } else {
                long[] top = busyHeap.poll();
                int room = (int) top[1];
                long earliest = top[0];
                count[room]++;
                busyHeap.add(new long[]{
                    earliest + (end - start), room});
            }
        }
        
        int result = 0;
        for (int i = 1; i < n; i++) {
            if (count[i] > count[result]) {
                result = i;
            }
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(m log m + m log n)

Sorting the m meetings takes O(m log m). For each meeting, we perform a constant number of heap operations (push/pop) on heaps of size at most n, each taking O(log n). The while loop that frees rooms processes each room at most once per meeting assignment, and across all meetings, each room is freed at most m times total (amortized). Overall: O(m log m + m log n). Since n ≤ 100 and log(100) ≈ 7, the heap operations are very fast in practice.

Space Complexity: O(n)

Both heaps together hold at most n entries (each room is in exactly one heap). The count array uses O(n) space. Total: O(n).

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

Meeting Rooms III

Description

Examples

Example 1

Example 2

Constraints

Editorial

Brute Force

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Optimal Approach - Two Min-Heaps

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis