Limited Time Offer:Up to 25% off Hello Interview Premium

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Low Level Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Ask The Community

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Tutor

Get Premium

Leetcode 2402. Meeting Rooms III

Assign each meeting (with unique start times) to the lowest-numbered available room or delay it (keeping its duration and prioritizing earlier original start times) until a room frees, and return the index of the room that hosted the most meetings. The core challenge is simulating this scheduling efficiently using priority queues to track free room indices and next-free times while counting assignments.

Asked at:

Google

DESCRIPTION

Input:

n = 2, meetings = [[0,10], [1,5], [2,7]]

Output:

Explanation: Room 0 hosts meetings 0 and 2 (2 meetings). Room 1 hosts meeting 1 (1 meeting). Room 0 has the most meetings, so return 0.

Constraints:

1 <= n <= 100 (number of rooms)
1 <= meetings.length <= 10^5
meetings[i].length == 2
0 <= start_i < start_i+1 (meetings sorted by start time)
1 <= duration_i <= 5 * 10^5
All start times are unique

Understanding the Problem

Let's understand what we're being asked to do. We have meetings with start times and durations, and a fixed number of rooms. Each meeting must be assigned to a room, but if all rooms are busy, the meeting gets delayed (keeping its duration) until a room becomes available.

For example, with 2 rooms and meetings [[0,10], [1,5], [2,7]]:

Meeting 0 starts at time 0, duration 10 → assigned to room 0 (ends at time 10)
Meeting 1 starts at time 1, duration 5 → assigned to room 1 (ends at time 6)
Meeting 2 starts at time 2, duration 7 → both rooms busy! Room 1 frees first at time 6, so meeting 2 is delayed to start at time 6 (ends at time 13)

Important constraint: Meetings are processed in order of their original start times (earliest first). If a meeting is delayed, it keeps its duration but starts when a room becomes available.

Key question: Which room hosted the most meetings? We need to count assignments per room and return the index of the room with the maximum count (if tied, return the lowest-numbered room).

Edge cases: What if all meetings fit without delays? What if one room is always chosen (lowest-numbered available)? What if multiple rooms tie for most meetings?

Brute Force Approach

For each meeting, scan through all rooms linearly to find the earliest available one. Track each room's next free time in an array. For each meeting, iterate through all rooms to find the one with the minimum free time (or the lowest index if multiple are free now). Update that room's free time and increment its meeting count. This approach is simple but inefficient because we repeatedly scan all rooms.

Visualization

def most_booked_room(n, meetings):
    """
    Brute force approach: For each meeting, scan all rooms linearly
    to find the earliest available one.
    """
    # Sort meetings by start time
    meetings.sort(key=lambda x: x[0])
    
    # Track next free time for each room
    room_free_time = [0] * n
    # Count meetings per room
    meeting_count = [0] * n
    
    # Process each meeting
    for meeting in meetings:
        start, end = meeting[0], meeting[1]
        duration = end - start
        
        # Scan all rooms to find earliest available
        best_room = -1
        earliest_free = float('inf')
        
        for room_idx in range(n):
            # Check if this room is better
            if room_free_time[room_idx] < earliest_free:
                earliest_free = room_free_time[room_idx]
                best_room = room_idx
            elif room_free_time[room_idx] == earliest_free:
                # Tie-breaker: prefer lower room number
                if room_idx < best_room:
                    best_room = room_idx
        
        # Schedule meeting in best room
        actual_start = max(start, room_free_time[best_room])
        room_free_time[best_room] = actual_start + duration
        meeting_count[best_room] += 1
    
    # Find room with most meetings
    max_meetings = max(meeting_count)
    for room_idx in range(n):
        if meeting_count[room_idx] == max_meetings:
            return room_idx
    
    return 0

Start meeting room scheduling

0 / 46

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n * m) For each of n meetings, we scan through all m rooms to find the best available one, resulting in O(n * m) time complexity

Space Complexity: O(m) We only need arrays to track free times and meeting counts for m rooms, using O(m) space

Building Intuition

At any moment, we need to know which room will be free next (to assign delayed meetings) and which room has the lowest index among currently free rooms (to assign meetings that can start on time).

This creates two distinct tracking needs: finding the minimum free time across all rooms, and finding the minimum room index among available rooms.

If we scan through all rooms linearly for each meeting to find the next available one, we'd spend O(n) time per meeting, leading to O(n * m) total time where n is meetings and m is rooms.

By organizing rooms into priority structures (one tracking free times, one tracking available indices), we can find the next room in O(log m) time instead of O(m), making the overall algorithm much more efficient for large inputs.

Imagine a hotel with multiple rooms. When a guest arrives:

If any rooms are currently vacant, assign the lowest room number (room 101 before room 102)
If all rooms are occupied, find which room will be vacated soonest, and reserve it for this guest (they wait until that room is ready)

You'd want two lists: one showing vacant room numbers (sorted by number), and one showing occupied rooms sorted by checkout time. This dual-tracking approach maps perfectly to using two priority queues.

Common Mistakes

Forgetting to check if rooms have freed up before assigning a new meeting - must compare meeting start time with room free times

Not handling tie-breaking correctly when multiple rooms are available - must always choose the lowest-indexed room

Incorrectly updating room free times - the new free time is max(current free time, meeting start) + duration, not just start + duration

Not maintaining the count array properly - must increment the count for the assigned room after each assignment

Confusing the two heaps' purposes - one tracks available rooms by index, the other tracks busy rooms by free time

Optimal Solution

Use two priority queues (heaps) to efficiently track room availability. The first min-heap tracks available room indices (prioritizing lower-numbered rooms). The second min-heap tracks busy rooms by their next free time (and room index for tie-breaking). For each meeting, check if any rooms have freed up by comparing their free time to the meeting's start time. Move freed rooms from the busy heap to the available heap. Then assign the meeting to the lowest-indexed available room (or the earliest-freeing busy room if none are available). This eliminates the need to scan all rooms linearly.

Visualization

import heapq
def most_booked_room(n, meetings):
    """
    Assign meetings to rooms using priority queues.
    Returns the room index that hosted the most meetings.
    """
    # Sort meetings by start time
    meetings.sort(key=lambda x: x[0])
    
    # Initialize room counters and heaps
    room_count = [0] * n
    available_rooms = list(range(n))  # Min-heap of available room indices
    heapq.heapify(available_rooms)
    busy_rooms = []  # Min-heap of (end_time, room_index)
    
    # Process each meeting
    for start, end in meetings:
        duration = end - start
        
        # Free up rooms that are available by this meeting's start time
        while busy_rooms and busy_rooms[0][0] <= start:
            end_time, room_idx = heapq.heappop(busy_rooms)
            heapq.heappush(available_rooms, room_idx)
        
        # Assign meeting to a room
        if available_rooms:
            # Use lowest-numbered available room
            room_idx = heapq.heappop(available_rooms)
            meeting_end = end
        else:
            # All rooms busy - use earliest-freeing room
            earliest_end, room_idx = heapq.heappop(busy_rooms)
            meeting_end = earliest_end + duration
        
        # Update room usage count and mark as busy
        room_count[room_idx] += 1
        heapq.heappush(busy_rooms, (meeting_end, room_idx))
    
    # Find room with maximum bookings
    max_bookings = max(room_count)
    for i in range(n):
        if room_count[i] == max_bookings:
            return i
    
    return 0

Start meeting room scheduling

0 / 24

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n log m) For each of n meetings, we perform heap operations (insert/extract) which take O(log m) time where m is the number of rooms. Total: O(n log m)

Space Complexity: O(m) We maintain two heaps and a count array, all of size proportional to the number of rooms m, using O(m) space

What We've Learned

Dual heap pattern for resource allocation: Use two min-heaps simultaneously - one tracking available resources (free room indices) and another tracking busy resources with release times (room index, end time). This pattern is essential when you need to allocate limited resources over time and always want the optimal choice (lowest room number when free, earliest available when all busy).
Event simulation with priority queues: Sort meetings by start time first, then simulate chronologically by advancing time to the next meeting and releasing all rooms that freed up before that meeting starts. The key insight is to process room releases in bulk before each allocation, avoiding unnecessary time-step iterations.
Tie-breaking in heap comparisons: When rooms become free at the same time, you must break ties by room index in your busy-rooms heap to ensure the lowest-numbered room is selected. Similarly, when meetings are delayed, maintain their original start time order for fair scheduling - this requires careful tuple ordering in your heap.
Meeting delay calculation pitfall: When all rooms are busy, the delayed meeting starts at `earliest_free_time`, not at its original start time. The critical mistake is forgetting to update the meeting's end time to `earliest_free_time + duration` rather than `original_start + duration`. Always recalculate based on actual start time.
Counting array optimization: Instead of storing which meetings went to which room, maintain a simple count array indexed by room number. After simulation, find the room with maximum count (ties broken by lowest index). This O(n) space approach is cleaner than tracking full assignment history.
Greedy scheduling pattern: This problem exemplifies greedy resource allocation with constraints - always choose the best available option (lowest room) at each decision point. This pattern extends to CPU scheduling, parking lot systems, and any scenario where you assign tasks to limited resources with availability windows.

Test Your Understanding

Why is heap the right data structure for this problem?

heap provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Late November, 2025

Google

Mid-level

Early June, 2025

Uber

Senior

Mid May, 2025

Google

Senior

Get Premium to View All 8 Reports

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 2402. Meeting Rooms III

DESCRIPTION

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact