Meeting rooms II with a min heap

Why this matters

A calendar tool gets a list of meetings, each with a start time and an end time. It must answer one question: how many meeting rooms does the office need so that no two meetings in the same room overlap? This question shows up in scheduling software, cloud job placement and interview practice. It is a good test of whether you can keep track of "what is busy right now" while you walk through a list.

This lesson uses a min heap for that tracking. The heap stores the end time of every room that is busy. The top of the heap is always the room that frees up first, so you can check it in one step. The lesson also shows a second method, a sweep over sorted start and end times, so you can compare the two and see the trade-off.

Earlier lessons in this module explain how a heap works. This lesson uses one and does not repeat that material.

Words used in this lesson

• Meeting: a pair of numbers {start, end}. The meeting is in the room from start up to, but not including, end. A meeting from 9 to 10 uses the room until 10, so another meeting can start at 10 in the same room.
• Room: one resource that can hold one meeting at a time.
• Busy room: a room whose current meeting has not ended yet.
• Min heap: a heap where the smallest value is at the top. Pushing a value and removing the top both take about log n steps, where n is the number of values in the heap.
• Sweep: a walk from left to right through a sorted list of events, keeping one running count as you go.

In C++, std::priority_queue is a heap. By default it puts the largest value at the top. To get a min heap you give it std::greater<int> as the comparison, which tells the heap to order values from smallest to largest.

#include <functional>
#include <queue>
#include <vector>
 
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

The three template arguments are the value type, the container that stores the heap, and the order. You will see this exact line in the code below.

Start with a small example

Take three meetings:

• meeting A runs from 0 to 30,
• meeting B runs from 5 to 10,
• meeting C runs from 15 to 20.

A and B overlap, because B starts at 5 while A is still running. So they need two rooms. C starts at 15. At that time B is over, since it ended at 10. A is still running, so one room is busy. C can use the room B left. The answer is 2.

You can also see this as a count. Look at the moment 7. Meetings A and B are both running, so the count is 2. Look at the moment 17. A and C are running, so the count is 2. No moment has three meetings running, so two rooms are enough. The number of rooms you need is the largest count of meetings running at the same moment.

That gives a slow method you could check by hand. For each moment in time, count the meetings that are running. Take the largest count. This works, but it checks every moment, so it is slow if times are large. The two methods below avoid that.

The idea: the room that frees first

Read the meetings in order of their start time. Keep a heap of the end times of the rooms that are busy. When a new meeting starts, look at the top of the heap. The top is the earliest end time among busy rooms.

• If the top end time is less than or equal to the new start time, the room with that end time is free. Remove the top and give the room to the new meeting. Then push the new meeting's end time.
• If the top is later than the new start time, every busy room is still in use. You need a new room. Push the new meeting's end time without removing anything.

The heap size is the number of rooms in use at that point. The answer is the largest size the heap ever reaches.

A min heap is used here, not a plain list. A list would force you to search every busy room to find the one that frees first. The min heap keeps that room at the top, so you check it in one step. When you pop it, the heap reorders itself in about log n steps. That is the whole reason for the heap in this problem.

Step by step by hand

Sort the meetings by start time first. For the example above the order does not change, because A starts at 0, B at 5 and C at 15. Here is the heap after each meeting. The heap is shown as its contents, smallest first.

The largest busy count is 2, so the answer is 2.

The first full program

This program does the work described above. It sorts the meetings by start time, keeps a min heap of end times and returns the largest heap size.

#include <algorithm>
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
 
struct Meeting {
    int start;
    int end;
};
 
// Min heap of end times: the top is the room that frees up first.
int minRoomsHeap(std::vector<Meeting> meetings) {
    std::sort(meetings.begin(), meetings.end(),
              [](const Meeting& a, const Meeting& b) { return a.start < b.start; });
 
    std::priority_queue<int, std::vector<int>, std::greater<int>> busyEnds;
    int best = 0;
    for (const Meeting& m : meetings) {
        if (!busyEnds.empty() && busyEnds.top() <= m.start) {
            busyEnds.pop();  // this room is free again, so reuse it
        }
        busyEnds.push(m.end);
        best = std::max(best, static_cast<int>(busyEnds.size()));
    }
    return best;
}
 
int main() {
    std::vector<Meeting> meetings = {{0, 30}, {5, 10}, {15, 20}};
    std::cout << "rooms needed: " << minRoomsHeap(meetings) << '\n';
}

Compile and run it with:

g++ -std=c++20 -Wall -o rooms rooms.cpp
./rooms

Output:

rooms needed: 2

Three details matter in this code.

• The function takes the vector by value. It sorts its own copy, so the caller's list keeps its original order.
• The check is <=, not <. A room whose meeting ends at 10 is free for a meeting that starts at 10. The next section shows what goes wrong with <.
• The line best = std::max(...) runs after the push. The size at that moment is the number of rooms in use, including the new meeting.

Second example: meetings that touch

Now a case where every meeting starts at the moment the previous one ends:

• A from 1 to 5,
• B from 5 to 8,
• C from 8 to 9,
• D from 2 to 3.

Sorted by start, the order is A (1 to 5), D (2 to 3), B (5 to 8), C (8 to 9).

• A: heap empty, push 5. Heap {5}, busy 1.
• D: top 5 is not at most 2, so push 3. Heap {3, 5}, busy 2.
• B: top 3 is at most 5, so pop 3 and push 8. Heap {5, 8}, busy 2.
• C: top 5 is at most 8, so pop 5 and push 9. Heap {8, 9}, busy 2.

The answer is 2. The room used by D is freed at 3, and it is reused by B. C reuses the room A frees at 5, but A and D overlap, so two rooms are needed in total.

The heap gives this answer with a two-element heap at every step. The heap never holds more than the answer, which is one reason the method is fast when most meetings do not overlap.

Third example: the sweep

The second method does not use a heap at all. It turns the meetings into two sorted lists, one of start times and one of end times, and walks through both with two indexes.

Think of the walk as a timeline of events. When the next start comes before the next end, a meeting begins and needs one more room. Otherwise a meeting ends and one room becomes free. The count of rooms moves up and down as you walk, and the answer is the highest count.

#include <algorithm>
#include <iostream>
#include <vector>
 
struct Meeting {
    int start;
    int end;
};
 
int minRoomsSweep(const std::vector<Meeting>& meetings) {
    std::vector<int> starts;
    std::vector<int> ends;
    for (const Meeting& m : meetings) {
        starts.push_back(m.start);
        ends.push_back(m.end);
    }
    std::sort(starts.begin(), starts.end());
    std::sort(ends.begin(), ends.end());
 
    int i = 0;      // next start to process
    int j = 0;      // next end to process
    int rooms = 0;  // rooms in use right now
    int best = 0;   // the most rooms in use at any moment
    while (i < static_cast<int>(starts.size())) {
        if (starts[i] < ends[j]) {
            ++rooms;
            ++i;
            best = std::max(best, rooms);
        } else {
            --rooms;
            ++j;
        }
    }
    return best;
}
 
int main() {
    std::vector<Meeting> meetings = {{0, 30}, {5, 10}, {15, 20}};
    std::cout << "rooms needed: " << minRoomsSweep(meetings) << '\n';
}

Trace it on the first example. The sorted starts are 0, 5, 15 and the sorted ends are 10, 20, 30.

• i=0, j=0: start 0 is less than end 10, so a meeting begins. rooms=1, best=1.
• i=1, j=0: start 5 is less than end 10, so rooms=2, best=2.
• i=2, j=0: start 15 is not less than end 10, so a meeting ends. rooms=1, j=1.
• i=2, j=1: start 15 is less than end 20, so rooms=2, best=2.
• i=3: the loop stops.

The answer is 2, the same as the heap method.

The comparison starts[i] < ends[j] is strict. When a start and an end have the same time, the end is handled first. That is the same rule as <= in the heap method: a room that ends at 10 is free for a start at 10.

Running it prints:

rooms needed: 2

Comparing the two methods

Both methods sort the meetings first, so both take about n log n steps for n meetings. What differs is the work after the sort.

• The heap method does one push for each meeting and at most one pop. Each push and pop costs about log k, where k is the number of busy rooms at that moment. For most inputs k is small, so this is cheap.
• The sweep does no heap work. After the two sorts it walks through 2n values once.

The heap method has one advantage. It knows which room frees up, because the heap holds the end time of each room. If the task were to say "meeting C goes in room 2", you could store a room number next to each end time in the heap. The sweep only counts rooms. It does not know which room is which, so it cannot give you a room assignment without more work.

The sweep has one advantage. It is simpler to get right, since it uses two plain sorted arrays and no heap. If you only need the number of rooms, many people write the sweep first and use the heap when the task asks for more.

In both methods the memory use is about n values for the meeting data plus the lists or heap. The heap never holds more values than the number of rooms in use, so its extra memory is at most n.

Common mistakes

Using < where <= is needed

If the check is busyEnds.top() < m.start, a room that ends at 5 is not reused by a meeting that starts at 5. The program then uses too many rooms. Here is the wrong version run on two meetings, A from 1 to 5 and B from 5 to 8:

strict [[1,5],[5,8]] = 2

The correct answer is 1, because A ends exactly when B starts. The bug is in one character, so check every comparison in this kind of problem against the rule for touching times.

Forgetting to sort by start time

The heap method needs the meetings in start order. If they are not sorted, a meeting can check a room that has not been freed yet, because a later meeting in the list would have freed it. Here is the same heap code on the list {5, 8}, {0, 10}, {1, 2} without sorting, and then with sorting:

unsorted [[5,8],[0,10],[1,2]] = 3
sorted   [[0,10],[1,2],[5,8]] = 2

Without sorting, the heap sees the meeting from 5 to 8 first, then the meeting from 0 to 10, which overlaps it. The meeting from 1 to 2 is then pushed onto a heap of two entries, which makes three, and the answer comes out too high. The two meetings from 0 to 10 and from 5 to 8 really do overlap, but the meeting from 1 to 2 ends before 5, so no moment has all three running. The correct answer is 2.

Using a max heap by mistake

std::priority_queue<int> without the std::greater<int> argument is a max heap. Its top is the largest end time, not the smallest. The check then looks at the wrong room. On the first example it gives 3 instead of 2:

max heap on [[0,30],[5,10],[15,20]] = 3

When the top is 30, the check 30 <= 15 fails, so the heap never frees a room, and it grows to 3. A quick way to catch this bug is to print the top after each push, and see whether it is the smallest value in the heap.

Missing the include for the heap

If #include <queue> is missing, g++ stops with this message:

noqueue.cpp: In function ‘int main()’:
noqueue.cpp:5:10: error: ‘priority_queue’ is not a member of ‘std’
    5 |     std::priority_queue<int> q;
      |          ^~~~~~~~~~~~~~

Add #include <queue> at the top of the file. Other forgotten standard headers give similar messages. The #include lines go at the top of the file, before the code that uses them.

A heap of meetings with no comparison

A common first attempt is std::priority_queue<Meeting> with the struct as the value type. C++ does not know how to order two Meeting values, so g++ rejects the code. The error names the operator it could not find. The path and line numbers depend on your g++ version:

/usr/include/c++/15/bits/stl_function.h:408:20: error: no match for ‘operator<’ (operand types are ‘const Meeting’ and ‘const Meeting’)

The fix is to store only the end times, as the code in this lesson does, or to write a comparison for Meeting. Storing end times is the simpler choice here, because the heap only needs end times.

Practice

Exercise 1: trace by hand

Sort these meetings by start time, then trace the heap method and give the answer: {2, 5}, {1, 3}, {4, 6}. Write the heap contents after each meeting.

Show the answer.

The sorted order is {1, 3}, {2, 5}, {4, 6}.

• {1, 3}: heap empty, push 3. Heap {3}, busy 1.
• {2, 5}: top 3 is not at most 2, so push 5. Heap {3, 5}, busy 2.
• {4, 6}: top 3 is at most 4, so pop 3 and push 6. Heap {5, 6}, busy 2.

The answer is 2. At time 4 to 5 the meetings {2, 5} and {4, 6} overlap, so two rooms are needed.

Exercise 2: the touching case

Predict the answer for {1, 3}, {3, 6}, {4, 5} using the rule that a room ending at time t is free for a meeting starting at t. Then check your answer with the code.

Show the answer.

The answer is 2. The meeting {1, 3} ends at 3, so {3, 6} can use its room. The meeting {4, 5} starts while {3, 6} is still running, so it needs a second room. The heap gives 2.

Exercise 3: a function that answers yes or no

Write a function bool oneRoomIsEnough(std::vector<Meeting> meetings) that returns true when no two meetings overlap. Use only a sort and a single loop, with no heap.

Show the answer.

bool oneRoomIsEnough(std::vector<Meeting> meetings) {
    std::sort(meetings.begin(), meetings.end(),
              [](const Meeting& a, const Meeting& b) { return a.start < b.start; });
    for (std::size_t i = 1; i < meetings.size(); ++i) {
        if (meetings[i].start < meetings[i - 1].end) {
            return false;  // this meeting starts before the previous one ends
        }
    }
    return true;
}

After sorting, a single room works only if each meeting starts at or after the end of the one before it. The test meetings[i].start < meetings[i - 1].end finds the first overlap. Remember to include <algorithm> and <vector>.

Exercise 4: find the bug

A student wrote this loop and gets the wrong answer on {1, 3}, {3, 6}. Find the bug and explain it in one sentence.

int best = 0;
for (const Meeting& m : meetings) {
    if (!busyEnds.empty() && busyEnds.top() < m.start) busyEnds.pop();
    busyEnds.push(m.end);
    best = std::max(best, static_cast<int>(busyEnds.size()));
}

Show the answer.

The check uses <, so the room ending at 3 is not reused by the meeting starting at 3. The heap grows to 2 and the answer is 2, but the correct answer is 1. The fix is to change < to <=.

Exercise 5: the sweep on a new input

Trace minRoomsSweep on {0, 10}, {1, 2}, {2, 3}, {3, 4}, {4, 5}, {9, 11}. Write the value of i, j, rooms and best after each step that changes them.

Show the answer.

The sorted starts are 0, 1, 2, 3, 4, 9. The sorted ends are 2, 3, 4, 5, 10, 11.

• start 0 is less than end 2: rooms 1, best 1, i=1.
• start 1 is less than end 2: rooms 2, best 2, i=2.
• start 2 is not less than end 2: rooms 1, j=1.
• start 2 is less than end 3: rooms 2, best 2, i=3.
• start 3 is not less than end 3: rooms 1, j=2.
• start 3 is less than end 4: rooms 2, best 2, i=4.
• start 4 is not less than end 4: rooms 1, j=3.
• start 4 is less than end 5: rooms 2, best 2, i=5.
• start 9 is not less than end 5: rooms 1, j=4.
• start 9 is less than end 10: rooms 2, best 2, i=6.

The loop ends and the answer is 2. Two rooms are busy from 1 to 5, and again from 9 to 10, so the answer is 2.

Summary

• The answer is the largest number of meetings running at the same moment.
• A min heap of end times keeps the room that frees up first at the top, so one check tells you whether a room can be reused.
• Sort meetings by start time before the heap loop, and use <= so a room is free at the exact moment its meeting ends.
• The sweep gives the same answer by sorting starts and ends separately and counting up and down.
• The heap method can also be extended to name rooms, which the sweep cannot do without more work.