#2402

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Meeting Rooms III

Determine which meeting room holds the most meetings by simulating room assignments with precise time tracking.

array hash table sorting heap priority queue simulation

Problem Statement

You are given n meeting rooms numbered from 0 to n - 1 and a list of meetings where each meeting has a unique start time and a defined end time. Each meeting is represented as [start, end) and must be assigned to the lowest-numbered available room at its start time, or delayed until a room is free.

If multiple meetings overlap, the next available room is chosen based on the earliest finish time. Track how many meetings each room holds and return the room index that hosted the most meetings, with ties broken by the smallest room number.

Examples

Example 1

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

Output: 0

At time 0, both rooms are not being used. The first meeting starts in room 0.
At time 1, only room 1 is not being used. The second meeting starts in room 1.
At time 2, both rooms are being used. The third meeting is delayed.
At time 3, both rooms are being used. The fourth meeting is delayed.
At time 5, the meeting in room 1 finishes. The third meeting starts in room 1 for the time period [5,10).
At time 10, the meetings in both rooms finish. The fourth meeting starts in room 0 for the time period [10,11). Both rooms 0 and 1 held 2 meetings, so we return 0.

Example 2

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

Output: 1

At time 1, all three rooms are not being used. The first meeting starts in room 0.
At time 2, rooms 1 and 2 are not being used. The second meeting starts in room 1.
At time 3, only room 2 is not being used. The third meeting starts in room 2.
At time 4, all three rooms are being used. The fourth meeting is delayed.
At time 5, the meeting in room 2 finishes. The fourth meeting starts in room 2 for the time period [5,10).
At time 6, all three rooms are being used. The fifth meeting is delayed.
At time 10, the meetings in rooms 1 and 2 finish. The fifth meeting starts in room 1 for the time period [10,12). Room 0 held 1 meeting while rooms 1 and 2 each held 2 meetings, so we return 1.

Constraints

1 <= n <= 100
1 <= meetings.length <= 105
meetings[i].length == 2
0 <= starti < endi <= 5 * 105
All the values of starti are unique.

Solution Approach

Sort meetings by start time

Sort the meetings array by the start times to ensure we always consider the earliest starting meeting first, which is critical for correctly simulating room assignments.

Simulate room allocation with a heap

Use a min-heap to track the end times of ongoing meetings for each room. Assign a meeting to the first available room or delay it until a room becomes free, updating the heap accordingly.

Count meetings per room

Maintain an array to count how many meetings each room holds. After processing all meetings, scan this array to determine the room with the maximum count, breaking ties by choosing the lowest room index.

Complexity Analysis

Metric	Value
Time	O(M \cdot \log M + M \cdot \log N + N \cdot \log N)
Space	O(N + sort)

Time complexity is O(M \cdot \log M + M \cdot \log N + N \cdot \log N) where M is the number of meetings and N is the number of rooms due to sorting and heap operations. Space complexity is O(N + sort) for the heap and the room counters.

What Interviewers Usually Probe

Focus on array scanning plus hash lookup for efficient room tracking.
Sort meetings before processing to avoid misallocation under overlap conditions.
Consider edge cases where multiple meetings finish simultaneously and tie-breaking matters.

Common Pitfalls or Variants

Common pitfalls

Forgetting to delay meetings when all rooms are busy.
Using a linear search for free rooms instead of a heap leading to TLE.
Not breaking ties correctly when multiple rooms have the same maximum meeting count.

Follow-up variants

Return the earliest time a specific room is free after all meetings.
Count the total delay time accumulated by all meetings.
Determine which room holds the least meetings instead of the most.

FAQ

What pattern does Meeting Rooms III primarily use?

Meeting Rooms III is an array scanning plus hash lookup problem where sorting by start times is crucial.

How do I handle overlapping meetings efficiently?

Use a min-heap to track room availability and delay meetings until the first room becomes free.

Can two rooms have the same maximum meetings?

Yes, in that case, return the room with the smallest index according to problem rules.

What is the best data structure for tracking room end times?

A min-heap is optimal for efficiently finding the earliest available room at any given time.

Why sort meetings first in Meeting Rooms III?

Sorting ensures meetings are processed in chronological order, which is critical for correct room allocation and simulation.

terminal

Solution

Solution 1: Priority Queue (Min-Heap)

We define two priority queues to represent idle meeting rooms and busy meeting rooms respectively. The idle meeting rooms $\textit{idle}$ are sorted by **index**; the busy meeting rooms $\textit{busy}$ are sorted by **end time and index**.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        meetings.sort(key=lambda x: x[0])
        busy = []
        idle = list(range(n))
        heapify(idle)
        cnt = [0] * n
        for s, e in meetings:
            while busy and busy[0][0] <= s:
                heappush(idle, heappop(busy)[1])
            i = 0
            if idle:
                i = heappop(idle)
                heappush(busy, (e, i))
            else:
                time_end, i = heappop(busy)
                heappush(busy, (time_end + e - s, i))
            cnt[i] += 1
        ans = 0
        for i in range(n):
            if cnt[ans] < cnt[i]:
                ans = i
        return ans

Continue Practicing

#2357 make array zero by subtracting equal amounts #2593 find score of an array after marking all elements #3080 mark elements on array by performing queries