LeetCode 253 · Intervals

Meeting Rooms II, explained with a picture

How many rooms does the office need?.

MediumIntervals
▶ Watch it step by step

The problem

Given meeting times, find the fewest rooms needed so every meeting has a room.

Input:  [0,30] [5,10] [15,20] [10,14] [25,35]
Output: 2

Picture it

Picture an office with rooms. Process meetings by start time. A min-heap holds the end times of meetings currently using rooms, earliest end on top. If the earliest-ending room is free by the time this meeting starts, reuse it; otherwise open a new room. The heap’s biggest size is the answer.

How to recognise it

  • You need the largest number of intervals active at the same moment: rooms, servers, cars in a car park, users online.
  • Each new interval can reuse a resource only if some earlier interval has finished, and the best one to check is the one that finishes earliest.
  • "Repeatedly give me the earliest end, and add new ends" is what a min-heap (a priority queue that returns its smallest item in O(log n)) does well.
  • A meeting that ends at 10 frees its room for a meeting that starts at 10.
  • Up to 10^4 meetings on LeetCode (a premium problem), so an O(n log n) sweep is expected.

Start with brute force

The busiest moment is always the start of some meeting (the count only rises at a start). So for each meeting's start time, count how many meetings are running then, and take the largest count.

def min_rooms_brute(intervals):
    best = 0
    for t, _ in intervals:               # the busiest moment is some start time
        busy = sum(1 for s, e in intervals if s <= t < e)
        best = max(best, busy)
    return best

s <= t < e treats a meeting as over at its end time, matching the back-to-back rule. Time is O(n²) and space O(1). For 10^4 meetings that is 10^8 checks, which takes several seconds in Python.

From brute force to the idea

  1. Find the waste. For every start time, the brute force recounts all meetings, although between two consecutive starts only a few meetings begin or end.
  2. Sweep in start order. Sort the meetings by start. Walk through them as the day goes on.
  3. Track when each room frees up. ends is a min-heap of the end times of rooms in use; ends[0] is the room that frees up first.
  4. Reuse or open. For a meeting starting at start: if ends[0] <= start, that room is free, so pop its old end. Then push this meeting's end, either into the reused room or into a new one.
  5. Read off the answer. Each step pops at most one end and always pushes one, so the heap never shrinks. Its final size is the largest number of rooms ever open at once, which is the answer.

This is the key idea: sort by start, keep a min-heap of end times, reuse the room that frees first, and the heap's size is the room count.

The key idea

Sort by start + min-heap of end times. O(n log n).

Python solution

def min_meeting_rooms(intervals):
    intervals.sort()
    ends = []                           # min-heap of when each room frees up
    for start, end in intervals:
        if ends and ends[0] <= start:
            heappop(ends)                 # reuse the room that frees first
        heappush(ends, end)
    return len(ends)

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from heapq import heappush, heappop

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n²): for each start, all meetings are countedO(1): a counter
Sort and min-heap (shown code)O(n log n): the sort, plus one push and at most one pop per meetingO(n): the heap can hold every meeting if all overlap

Edge cases

  • One meeting: one room.
  • Back to back ([[1, 5], [5, 10]]): 5 <= 5, so the room is reused: 1.
  • All overlapping ([[1, 10], [2, 10], [3, 10]]): no room ever frees, so 3.
  • LeetCode's example ([[0, 30], [5, 10], [15, 20]]): 2. [15, 20] reuses the room freed by [5, 10].
  • Unsorted input ([[7, 10], [2, 4]]): sorting first gives 1.
  • No meetings: LeetCode guarantees at least one, but the shown code returns 0 for [] without error.
  • The input is changed by sort(), and the code needs from heapq import heappush, heappop.

Common mistakes

  • Using < instead of <=, so a meeting starting exactly when another ends gets a new room.
  • Popping all finished rooms with a while loop and then returning len(ends). The heap then shrinks, so you must track the largest size separately.
  • Sorting by end instead of start. Meetings are then not processed in the order they begin, and the count can be wrong.
  • Using a plain list and min() instead of a heap, which makes each step O(n) and the whole O(n²).
Your turn: rooms need cleaning

After every meeting a room needs c minutes of cleaning before the next meeting can use it. Find the fewest rooms. For [[0, 10], [10, 20]] the answer is 1 with c = 0 and 2 with c = 5. Describe your approach, then write it if you like.

Compare with our answer

A room is busy until end + c, not end. Push that time into the heap instead; everything else stays the same.

from heapq import heappush, heappop

def min_rooms_cleaning(intervals, c):
    ends = []
    for start, end in sorted(intervals):
        if ends and ends[0] <= start:
            heappop(ends)
        heappush(ends, end + c)
    return len(ends)

Time O(n log n), space O(n).

A strong answer mentions: the room's free time becoming end + c, that the rest of the algorithm is unchanged, and using sorted so the caller's list is not modified.

Check what stuck

1. A log has login and logout times for 10^5 sessions. You need the largest number of users online at the same time. Which approach fits best?

2. Why can the shown code return len(ends) at the end, even though rooms free up during the day?

3. A learner writes ends[0] < start. Which input now gives a wrong answer?

Score 60% or more and the lesson is marked complete.