L3 · FAANGIntervals & greedy~15 min · 5 tests

Meeting Rooms II: Minimum Rooms Needed

Q: What is the time complexity of Meeting Rooms II: Minimum Rooms Needed in Python?

The optimal solution runs in O(n log n) time and O(n) auxiliary space. Sorting plus one heap operation per meeting.

Q: What is the brute-force approach, and how do you optimise it?

Min-heap of end times: O(n log n) time, O(n) space. The heap size is the number of rooms in use. Two sorted arrays sweep: O(n log n) time, O(n) space. Walk starts and ends; +1 on a start, −1 on an end.

Q: What follow-up questions do interviewers ask about Meeting Rooms II: Minimum Rooms Needed?

Return which room each meeting gets. Can one person attend all meetings? (Meeting Rooms I)

Find the minimum number of meeting rooms for overlapping meetings with a min-heap of end times in O(n log n), or a sweep over sorted starts and ends.

The problem

meetings is a list of [start, end]. Return the minimum number of rooms needed so no two meetings in the same room overlap. A meeting ending at t frees its room for one starting at t.

Examples

Example 1

Input

min_rooms([[0, 30], [5, 10], [15, 20]])

Expected output

Example 2
Input
```
min_rooms([[7, 10], [2, 4]])
```
Expected output
```
1
```

+ 3 hidden tests on Submit — back-to-back share a room.

Edge cases to ask about

Back-to-back meetings
All overlapping

Hints

0/3

How an interviewer scores this

0/9

1. Understand the problemRestate it, ask about edge cases and input size.
2. Write a brute-force solutionCorrect first, clever later.
3. Get the correct outputautoAll visible examples pass.
4. Analyse time complexityautoCommit to a Big-O in the Complexity Lab.
5. Analyse space complexityautoExtra memory, not the input.
6. Identify the bottleneckautoMeasure your code — where does it bend?
7. OptimiseUsually: a set or dict instead of a scan.
8. Explain why it worksSay it out loud to Solvi.
9. Test the edge casesautoSubmit passes every hidden test.

Python 3.13 · min_rooms

def min_rooms(meetings):
    """Minimum rooms so no meetings in a room overlap."""
    # Write your solution here
    pass

⌘/Ctrl + Enter runs the examples

Your code runs in real CPython inside your browser — nothing is sent anywhere. The first run downloads the interpreter (about 6 MB, once). Your code is saved on this device as you type.

Complexity Lab

What does this cost as n grows?

Interviewers score the analysis as much as the code. Commit to an answer first — then check it, and measure your code against the optimal one at growing input sizes.

Time complexity of the optimal solution

Space complexity (extra memory)

Pick both to reveal the answer.

Measure it

Runs the function on inputs of size 250 up to 16,000 and records the time and peak memory. Slow solutions stop early — a short curve is itself the answer.

From brute force to optimal

The progression an interviewer wants to hear, one step at a time.

Approach	Time	Space	Idea
Min-heap of end times	O(n log n)	O(n)	The heap size is the number of rooms in use.
bestTwo sorted arrays sweep	O(n log n)	O(n)	Walk starts and ends; +1 on a start, −1 on an end.

Walkthrough of the optimal approach (try it yourself first)

Sort by start. Keep a min-heap of end times for rooms in use. For each meeting, if the earliest-ending room is free (ends[0] <= start), reuse it (heapreplace); otherwise open a new room. The heap's final size is the answer.

Equivalent sweep: sort all starts and all ends separately; the peak of (starts seen − ends seen) is the answer.

Complexity: O(n log n) time, O(n) space. Sorting plus one heap operation per meeting.

Reveal the reference solution

import heapq

def min_rooms(meetings):
    ends = []
    for start, end in sorted(meetings):
        if ends and ends[0] <= start:
            heapq.heapreplace(ends, end)     # reuse the room that frees up first
        else:
            heapq.heappush(ends, end)
    return len(ends)

Follow-ups interviewers ask

Return which room each meeting gets.
Can one person attend all meetings? (Meeting Rooms I)

Frequently asked interview questions

Core interview concepts, complexities, and follow-ups scored by hiring teams.

What is the time complexity of Meeting Rooms II: Minimum Rooms Needed in Python?