Meeting rooms II with a min heap in Python

Why it matters

Imagine a shared calendar for a company with a few meeting rooms. Someone asks: "What is the fewest rooms we need so that every meeting gets a room?" You could try to answer by hand for ten meetings. For ten thousand meetings you need a method.

This question is a common interview problem, and it is also a real scheduling question. Booking systems, cloud job schedulers and cinema seat planners all ask how many resources are busy at the same moment. The answer is the peak number of overlapping jobs.

This lesson uses a heap in a new way. The earlier lessons on top-k values in this module used a heap to keep the best few values. Here the heap keeps the end times of the rooms that are still busy, so its size at any moment is the number of rooms in use.

By the end of this lesson you will be able to count rooms with a min heap, trace the heap by hand for a small example, and explain why the same answer can also come from a sorting method that uses no heap at all.

The problem in plain words

A meeting is a pair of numbers: a start time and an end time. Times are plain integers here, such as 9 for 9:00. A meeting from 9 to 10 is written (9, 10) in Python, a tuple of two values. A tuple is a fixed group of values in order. You read the start with meeting[0] and the end with meeting[1].

Two meetings overlap when they both use a room at the same moment. The meeting (0, 30) and the meeting (5, 10) overlap, because both are running at minute 6.

A meeting ends at its end time and does not use the room at that moment. So (0, 30) and (30, 60) do not overlap. The first room is free at minute 30, and the second meeting can start there. This rule matters a lot, and a later section shows what goes wrong when it is ignored.

The task is: given many meetings, return the smallest number of rooms that lets every meeting happen.

Take this input:

(0, 30), (5, 10), (15, 20)

Draw the three meetings on a timeline:

time:   0    5   10   15   20   30
        |----|----|----|----|----|
(0,30)  ###########################
(5,10)       #####
(15,20)                 #####

Between minute 5 and minute 10, two meetings run at once. So at least two rooms are needed. The third meeting starts at 15, after the second has ended at 10, so it can use the second room. The answer is 2.

A first idea and why it is slow

The simplest check is to compare every pair of meetings and see whether they overlap. That shows whether two meetings clash, but it does not tell you the number of rooms for the whole set. You would also need to know which meetings share a moment with which others.

A more useful question is this: at each start time, how many meetings are already running? The largest count at any start time is the answer. You can check it by looking at each meeting's start and counting the meetings that cover that moment. That check takes time proportional to the square of the number of meetings, which is too slow for big inputs.

The better idea is to go through the meetings in start order and keep track of the rooms that are busy. When a new meeting starts, some busy rooms may already be free, because their meetings ended. A free room can be reused. If no room is free, a new room is needed.

The open question is which busy room to check first. The room that frees up soonest is the one with the earliest end time. A min heap (defined in the next section) gives that value immediately.

What a min heap is

A heap is a tree-shaped structure stored in a list. It keeps one value at the top that is always the best. In a min heap, the top is always the smallest value. In a max heap, the top is the largest.

Python has no heap type of its own. The standard library module heapq turns a plain list into a min heap. You import it once and then use four operations on the list:

• heapq.heappush(h, x) puts a value in the heap. It takes about log n steps.
• h[0] returns the smallest value without removing it. It takes one step. This is the "peek".
• heapq.heappop(h) removes and returns the smallest value. It takes about log n steps.
• len(h) returns the number of values in the heap. It takes one step.

Here n is the number of values in the heap. The term log n means the number of times you can cut n in half before you reach 1. For a heap of 1,000 values that is about 10 steps, which is why heaps stay fast even when they grow large.

The list is not sorted, and the code must not treat it as sorted. Only the value at index 0 is guaranteed to be the smallest. The next section shows what the list looks like.

If you have used Java, its PriorityQueue plays the same role as heapq.

The idea, built step by step

Sort the meetings by start time. Then process them one at a time. Keep a min heap where each value is the end time of a room that is still busy.

For each meeting, in order:

1. Look at the smallest end time in the heap, which is h[0]. If it is less than or equal to this meeting's start, that room has become free. Remove it from the heap.
2. Add this meeting's end time to the heap. This means the room the meeting uses is now busy until that end time.
3. Record the heap's size. That size is the number of rooms busy right now.

The answer is the largest size seen at any step.

The heap size equals the number of rooms in use. Each value in the heap stands for one busy room, and the value is the time that room becomes free. The rooms that have already finished were removed in step 1. So after step 2, the heap holds exactly the rooms that are busy at this meeting's start time.

Worked example by hand

Use the three meetings from earlier: (0, 30), (5, 10) and (15, 20). They are already sorted by start time, so you can process them in the order given.

Start with an empty list.

1. Meeting (0, 30). The list is empty, so nothing is freed. Push 30. The list is [30]. Size is 1. The largest so far is 1.
2. Meeting (5, 10). The smallest end time is 30. Is 30 less than or equal to 5? No, so no room is freed. Push 10. The list is [10, 30]. Size is 2. The largest so far is 2.
3. Meeting (15, 20). The smallest end time is 10. Is 10 less than or equal to 15? Yes, so that room is free. Pop 10. The list is [30]. Push 20. The list is [20, 30]. Size is 2. The largest is still 2.

The answer is 2. The same number came out of the timeline drawing, which is a good sign that the method matches the real problem.

The Python code

This is the complete method. Read it once, then run it.

Some details in this code need explaining.

sorted(meetings, key=lambda m: m[0]) returns a new list, sorted by the start time. The original list is not changed, so a caller who passed in their own list does not see it reorder. The key part tells sorted to compare meetings by their first number. The lambda is a short unnamed function. Each m is one tuple such as (5, 10).

end_times is a plain list used as a heap. The code calls heapq.heappush to add and heapq.heappop to remove the smallest. The check end_times[0] reads the smallest value without removing it.

The while loop, not an if, frees every room that has finished. This makes the heap size exactly the number of busy rooms. With an if in place of while, one finished room is freed per meeting, so a heap can keep finished rooms. The mistakes section shows this.

max(best_so_far, len(end_times)) keeps the largest heap size seen. The final heap size is not the answer. The heap can shrink later, so only the peak counts.

list[tuple[int, int]] in the signature is a type hint. It says the function takes a list of pairs of integers. Python does not check it at run time.

To run the file, save it as meeting_rooms.py and use this command:

python3 meeting_rooms.py

The output below was made with Python 3.14.4:

heap: 2
heap: 1
heap: 1

The second example has meetings (7, 10) and (2, 4). They do not overlap, so one room is enough. The third example has three meetings that meet end to start at 30 and 60. Each room is free exactly when the next meeting starts, so one room is enough.

Second example: meetings that share a boundary

The third example in the code's list shows a rule that is easy to get wrong. The meetings (0, 30) and (30, 60) share the minute 30. The first ends at 30, and the second starts at 30.

Using the while rule with <=, the room becomes free at 30, and the second meeting reuses it. The heap works like this:

1. (0, 30): list [30], size 1.
2. (30, 60): the smallest end time is 30, and 30 is less than or equal to 30. Pop it. Push 60. List [60], size 1.

The answer is 1. If you had written < instead of <=, the room would stay busy for one more moment and the answer would be 2. The mistakes section shows that output.

Third example with rooms that grow and are reused

Here is a harder input. Five meetings overlap in a chain, and the rooms come free and are reused.

(1, 4), (2, 5), (3, 6), (4, 7), (5, 8)

Work through the heap by hand.

1. (1, 4): list [4], size 1.
2. (2, 5): smallest end is 4. Is 4 at most 2? No. Push 5. List [4, 5], size 2.
3. (3, 6): smallest end is 4. Is 4 at most 3? No. Push 6. List [4, 5, 6], size 3.
4. (4, 7): smallest end is 4. Is 4 at most 4? Yes, pop it. List [5, 6]. Push 7. List [5, 6, 7], size 3.
5. (5, 8): smallest end is 5. Is 5 at most 5? Yes, pop it. List [6, 7]. Push 8. List [6, 7, 8], size 3.

The answer is 3. You can check this against the timeline: at minute 3, the meetings (1, 4), (2, 5) and (3, 6) all run. No moment has four meetings running at once, so 3 is correct.

The heap never grows past 3 here, even though five meetings were processed. Rooms were freed at steps 4 and 5 and reused. This is the main point of the method: the heap size tracks rooms in use, not meetings processed.

The sorted-events sweep

There is a second way to get the same answer, and it uses no heap. It is called a sweep. Think of a line of events on a timeline. Each start adds one busy room, and each end removes one.

The idea is to sort all the start times and all the end times separately. Then walk through the starts in order, and before each start, remove every end time that has already passed. The count of busy rooms at each start is then known, and the largest count is the answer.

The code is the min_rooms_sweep function in the program above. Its first two lines build two sorted lists, one of starts and one of ends:

starts = sorted(start for start, _ in meetings)
ends = sorted(end for _, end in meetings)

The _ name is a convention for "a value I do not use". The generator expression start for start, _ in meetings walks the pairs and keeps only the start of each.

Trace it on (0, 30), (5, 10), (15, 20). The sorted starts are 0, 5, 15. The sorted ends are 10, 20, 30.

• Start 0. No end is at or before 0. Busy becomes 1. Best is 1.
• Start 5. The end 10 is not at or before 5. Busy becomes 2. Best is 2.
• Start 15. The end 10 is at or before 15, so busy drops to 1. The end 20 is not at or before 15. Busy becomes 2. Best is 2.

The answer is 2, which matches the heap method.

The starts and ends are sorted separately. Each meeting's start and end belong to the same meeting, but the sweep does not need to know which end goes with which start. It only needs to know how many rooms are busy at each moment. Sorting the two lists separately lets it count starts and ends in time order without pairing them.

Comparing the two methods

Both methods produce the same answer. A brute-force checker, which counts overlaps at every start time directly, agreed with both methods on 20,000 random cases. Each case had between 1 and 8 meetings, with starts from 0 to 20 and lengths from 1 to 8 minutes.

These are the practical differences:

• The sweep only counts. It returns the number of rooms and nothing more. It is short and uses two plain lists of integers.
• The heap method keeps the actual end times of the busy rooms. That is what you need if you also want to assign room numbers, or to know which room frees up next. The same heap can be reused for those extra questions.
• Both methods sort first, so both take about n log n time. The heap method also does about n heap operations, each taking about log n steps. The sweep does one linear pass after sorting.
• The heap holds up to n values in the worst case. The sweep stores two lists of n integers each.

When you only need the count, the sweep is the simpler tool. When you need to know which room is free next, the heap is the right one.

Common mistakes

Forgetting to sort the meetings

The heap method depends on processing meetings in start order. If the meetings are not sorted, a room can look busy when it is actually free, and the heap grows too large.

Here is the same loop without the sorted call, run on this input:

(5, 6), (0, 10), (1, 2)

without sort: 3 with sort: 2

Without the sort, the method reports 3 rooms. The correct answer is 2. The meeting (5, 6) was added first, so the room ending at 6 was still in the heap when (1, 2) was checked. Sorting first puts (0, 10) and (1, 2) before (5, 6), and the answer comes out right.

Using < instead of <=

If you free a room only when its end time is strictly less than the start, back-to-back meetings need two rooms. Here is the output from that version on (0, 30) and (30, 60):

strict < on back-to-back: 2 correct: 1

The rule is that a meeting ending at 30 frees the room at 30. The check must be end_times[0] <= start.

Using if instead of while

With an if, only one finished room is removed per meeting. Take the meetings (0, 1), (0, 1) and (2, 3). After the first two, the heap is [1, 1]. At the third meeting, the if removes one 1 and then pushes 3. The heap is left as [1, 3], with two values, while only one meeting is running at minute 2.

For this input the final answer is still 2, because the peak was reached at minute 0. The heap contents are still wrong, though, and a later step can rely on them. Use while.

Reading the heap as a sorted list

The list inside the heap is not in sorted order. Pushing 30, 10 and 20 in that order gives this list:

import heapq
 
h = []
for x in [30, 10, 20]:
    heapq.heappush(h, x)
print("heap list:", h)
print("sorted:", sorted(h))
print("heap[0]:", h[0])

The output is:

heap list: [10, 30, 20]
sorted: [10, 20, 30]
heap[0]: 10

Only h[0] is the smallest value. The other values are in an order that keeps the heap fast to update, and it is not a sorted order. To read all the values in order, pop them one at a time with heapq.heappop.

Reading the heap when it is empty

heapq has no separate peek function, so end_times[0] is the peek. On an empty list it fails. If the while loop checked only the end time and not end_times first, the first meeting would crash:

end_times = []
start = 0
while end_times[0] <= start:
    heapq.heappop(end_times)

Python stops and prints the last line of the error:

IndexError: list index out of range

The check while end_times and end_times[0] <= start: is safe because Python stops at and when the list is empty, so end_times[0] never runs.

Putting dictionaries in a heap

A heap needs values it can compare with <. Numbers and tuples of numbers work. A dictionary does not, so this fails once the heap has two values to compare:

heap = [{"end": 5}]
heapq.heappush(heap, {"end": 3})

Python prints this error:

TypeError: '<' not supported between instances of 'dict' and 'dict'

The fix is to store the value that the heap should compare, such as the end time, or a tuple whose first item is the value to compare.

Practice

Each exercise has its answer below it. Try each one on paper before you read the answer.

Exercise 1: trace the heap

Trace the heap method on (1, 5), (2, 3), (4, 6). Write the list after each meeting, and give the answer.

Show the answer

After (1, 5) the list is [5], size 1. For (2, 3) the smallest end is 5, which is not at most 2, so push 3. The list is [3, 5], size 2. For (4, 6) the smallest end is 3, which is at most 4, so pop it. The list is [5]. Push 6. The list is [5, 6], size 2. The answer is 2. A brute-force check of the overlaps gives the same result: at minute 2 the first two meetings run together, and at minute 4 the first and third do.

Exercise 2: predict the answer for back-to-back meetings

What does the method return for (0, 5), (5, 10), (5, 10)? Explain why.

Show the answer

The answer is 2. After (0, 5) the list is [5]. The meeting (5, 10) starts at 5. The end 5 is at most 5, so that room is freed and the heap is empty. Then 10 is pushed, and the list is [10]. Then the third meeting (5, 10) starts at 5 again. The end 10 is not at most 5, so nothing is freed. The list becomes [10, 10], size 2. Two meetings run from 5 to 10, so two rooms are needed.

Exercise 3: check for a single room

Write a function fits_in_one_room(meetings) that returns True when every meeting fits in one room. Use the heap method's result, and then write a second version that does not use min_rooms.

Show the answer

Using the existing function:

def fits_in_one_room(meetings: list[tuple[int, int]]) -> bool:
    return min_rooms(meetings) <= 1

Without min_rooms, sort the meetings by start time and check that each meeting starts at or after the previous one ends:

def fits_in_one_room_sorted(meetings: list[tuple[int, int]]) -> bool:
    ordered = sorted(meetings, key=lambda m: m[0])
    for i in range(1, len(ordered)):
        if ordered[i][0] < ordered[i - 1][1]:
            return False
    return True

The second version works because one room means no two meetings overlap. In sorted order, an overlap between two meetings always shows up as an overlap between a meeting and the one right after it, so checking neighbours is enough. The two versions agree on [(0, 5), (5, 9)], which returns True from both, and on [(0, 5), (4, 9)], which returns False from both.

Exercise 4: explain why the sweep sorts the lists separately

The sweep sorts the starts and the ends in two separate lists. Explain in your own words why it does not need to pair each start with its own end.

Show the answer

The sweep only needs to know how many rooms are busy at each start time. Before each start, it removes the ends that have already passed. Each end removes one busy room, no matter which meeting it came from. Two sorted lists are enough to count the starts and ends in time order. Pairing them would be extra work that the count does not need.

Exercise 5: find the peak with a larger input

Predict the answer for (1, 10), (2, 3), (3, 4), (4, 5), (5, 6). Then check your answer with the method.

Show the answer

The answer is 2. The long meeting (1, 10) is always busy. Each short meeting starts at the moment the previous one ends, so only one short meeting runs alongside the long one at a time. At minute 2 the first two meetings run together, and at minute 3 the long one and the meeting (3, 4) run together. No moment has three meetings running. The method returns 2, and the list never holds more than 2 values.

Summary

• A min heap of end times tracks the rooms that are busy. Its size is the number of rooms in use at each start.
• Sort the meetings by start time, pop every room whose end time is at most the start, then push the new end time.
• The answer is the largest heap size seen during the loop, not the size at the end.
• A meeting that ends at 30 frees its room for a meeting that starts at 30, so the check is end_times[0] <= start.
• The sorted-events sweep gives the same count with no heap. It is simpler when only the count matters.