NeetCode #838LC-2402HardIntervalsNC 250
← Back to All Problems#838 · #2402 · Meeting Rooms III(会议室 III)
📌 Problem Statement & Constraints
You are given
n rooms numbered 0 to n-1 and a list of meetings [start, end]. Rooms are assigned to the lowest-numbered free room; if none is free the meeting is delayed until the earliest room frees, keeping the same duration. Return the room that hosted the most meetings (lowest index on ties). Constraints: 1 <= n <= 100, 1 <= meetings.length <= 10^5, 0 <= start < end <= 5 * 10^5.💡 Core Algorithmic Approaches
- Sort meetings by start time and simulate with two heaps: a min-heap of free room indices and a min-heap of
(endTime, room)for busy rooms. - Before seating each meeting, move every room whose end time is at or before the start into the free heap.
- If a free room exists, take the smallest index; otherwise the meeting waits, so pop the earliest-finishing busy room and reschedule it to
freeTime + duration. - Count usage per room and return the room with the maximum count, breaking ties by index.
💻 Benchmark Python3 Implementation
class Solution:
def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
import heapq
meetings.sort()
free = list(range(n))
heapq.heapify(free)
busy = [] # (end time, room)
cnt = [0] * n
for start, end in meetings:
while busy and busy[0][0] <= start:
_, room = heapq.heappop(busy)
heapq.heappush(free, room)
if free:
room = heapq.heappop(free)
heapq.heappush(busy, (end, room))
else:
free_at, room = heapq.heappop(busy)
duration = end - start
heapq.heappush(busy, (free_at + duration, room))
cnt[room] += 1
best = max(cnt)
return cnt.index(best)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(m log m + m log n): sorting the meetings plus heap operations per meeting.
💾 Space Complexity
O(n + m): the two heaps and the usage counter.
⚠️ Interview Pitfalls & Follow-ups
- Keeping the original end when delaying: a delayed meeting still runs for its original duration, so the new end is
freeTime + (end - start). - Using
busy[0][0] < start: a room freeing exactly at the start is available, so the test is<=. - Choosing the smallest-index free room with a set: a min-heap of indices gives the smallest room in O(log n).
- Ignoring the tie-break: when two rooms have the same count the smaller index wins, which
cnt.index(max(cnt))provides.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.