How to Solve Meeting Rooms III

Start by sorting meetings by start time and simulate room usage with a min-heap to track availability. Use a hash map or array to count meetings per room. Finally, identify the room with the maximum meetings, handling tie-breaking by the smallest room index.

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

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.

How GhostInterview Helps

• Automatically sorts and simulates meeting assignments for you, ensuring heap and array logic is correct.
• Tracks per-room meeting counts and highlights tie-breaking situations for faster answers.
• Provides step-by-step reasoning to avoid common array scanning and hash table mistakes.

Topic Pages

• Array
• Hash Table
• Sorting
• Heap (Priority Queue)
• Simulation

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.