⚡Flashcard Drill➔
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

  1. 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.
  2. Before seating each meeting, move every room whose end time is at or before the start into the free heap.
  3. 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.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Intervals Problems