LESSON 349 OF 409 · GREEDY

Meeting Rooms II in C++: Sorting Start and End Events

Practice O(n log n) Read the full explanation

Given an array consisting of meeting time intervals, which are represented by the start and end times [[s0, e0], [s1, e1], ...], determine the minimum number of meeting rooms needed in order to be able to accommodate all meetings at every moment of time.

Example:

Input: [[5, 10], [0, 30], [15, 20]]
Output: 2
Explanation: 1st and 3rd meetings can be assigned to the first room
             2nd meeting can be assigned to room 2

Note:

You may assume the interval's end point is always greater than its start point.
Intervals like [1,2] and [2,3] have borders "touching" but they don't overlap.

Your algorithm should run in O(n log n) time and use O(n) extra space.

STEP 1 OF 12

Guided

Ctrl + Enter to check

C++ · GREEDY

Meeting Rooms in C++, explained

Problem overview

The method meetingRooms receives intervals, a vector<vector<int>> in which each inner vector is [start, end] for one meeting. It returns the minimum number of rooms needed so that every meeting has a room for its whole duration. Two meetings need different rooms only if they overlap in time. The end of a meeting is always later than its start, and meetings that touch, such as [1, 2] and [2, 3], do not overlap, so they can share a room.

In the example, intervals = [[5, 10], [0, 30], [15, 20]]. The meeting from 0 to 30 lasts the whole time, so it always occupies one room. The other two meetings never overlap each other, so they share a second room. The answer is 2.

The statement asks for O(n log n) time and O(n) extra space.

Approach: count the meetings that are running at once

The number of rooms you need is the largest number of meetings that are in progress at the same moment. If at some moment four meetings overlap, four rooms are unavoidable. And if never more than four overlap, four rooms are enough.

Comparing every pair of meetings to find overlaps would cost O(n^2). A faster way is to turn the meetings into events and sweep through time:

every meeting produces a start event, which adds one running meeting;
every meeting produces an end event, which removes one running meeting.

Sort all the events by time and process them in order, keeping a counter of the running meetings. The largest value the counter ever reaches is the answer. Sorting 2n events costs O(n log n), and the sweep is a single pass.

To make the counter update trivial, each event is a pair (time, type), where the type is +1 for a start and -1 for an end. Processing an event is then just count += type.

Events at the same time

When a meeting ends at the same moment another one starts, the two do not overlap, so the ended meeting must be removed before the new one is added. Otherwise the counter would briefly show an overlap that does not exist. That is why events with equal times are ordered by type, with -1 before +1. With the intervals [1, 2] and [2, 3], the events are (1, +1), (2, -1), (2, +1), (3, -1). The counter goes 1, 0, 1, 0, so one room is enough. If the start came first at time 2, the counter would reach 2, and the answer would be wrong.

The example, event by event

For [[5, 10], [0, 30], [15, 20]] the sorted events and the counter are:

Event	(time, type)	Running meetings
1	(0, +1)	1
2	(5, +1)	2
3	(10, -1)	1
4	(15, +1)	2
5	(20, -1)	1
6	(30, -1)	0

The maximum is 2.

Step by step

Declare events as a vector<pair<int, int>>. Each pair holds a time in first and a type in second.
Loop over intervals with a range-based for, using auto for the element type, which is a vector<int>.
Push the start event {interval[0], 1} with push_back. A braced list converts to the vector's element type, a pair<int, int>.
Push the end event {interval[1], -1} the same way.
Sort the events with sort(events.begin(), events.end(), ...) and a lambda. It returns true when a must come first: if the times are equal, compare the types with a.second < b.second, so -1 goes first. Otherwise compare the times.
Declare answer and noOfMeetings in one statement, both set to 0. noOfMeetings counts the meetings in progress, and answer keeps the largest count.
Sweep the sorted events with a range-based for that unpacks each pair into auto [time, type].
Add the type to the counter with noOfMeetings += type. A start adds 1 and an end subtracts 1.
Update the maximum with answer = max(answer, noOfMeetings), and return answer after the loop, once every event has been processed.

The solution in C++

class Solution {
public:
    int meetingRooms(vector<vector<int>>& intervals) {
        vector<pair<int, int>> events;
        for (auto interval : intervals) {
            events.push_back({interval[0], 1});
            events.push_back({interval[1], -1});
        }
        
        sort(events.begin(), events.end(), [](auto &a, auto &b) {
            if (a.first == b.first) {
                return a.second < b.second;
            }
            return a.first < b.first;
        });
        
        int answer = 0, noOfMeetings = 0;
        for (auto [time, type] : events) {
            noOfMeetings += type;
            answer = max(answer, noOfMeetings);
        }

        return answer;
    }
};

The C++ details worth knowing:

The comparison must be a strict "less than". sort needs a function that returns false for equal elements. The lambda does that: equal pairs fall through both comparisons and return false. A comparison written with <= breaks the rules of sort and can crash on some inputs.
The lambda is a rule that std::pair already follows. Pairs compare first and then second, so sort(events.begin(), events.end()) with no lambda gives the same order. The lambda spells the rule out.
auto parameters in a lambda (C++14) make it generic, so the types of a and b do not have to be written out. Taking them as const auto & is the safer habit, because it also accepts constant elements, and a comparison should never change what it compares.
for (auto interval : intervals) copies each inner vector. Writing const auto &interval reads the same data without the copies. The result is identical.
Structured bindings (C++17) in auto [time, type] name the two members of each pair. The variable time is unused apart from the unpacking, which is fine.
A comma in one declaration. int answer = 0, noOfMeetings = 0; declares two separate variables of the same type.

Complexity

Time: O(n log n). Building the events is O(n). Sorting 2n events costs O(n log n). The sweep over them is O(n). The sort dominates.

Space: O(n). The events vector holds two pairs per meeting. The sort itself works in place on that vector apart from a small amount of stack space.

A common alternative sorts the meetings by start time and keeps a min-heap of the end times of the meetings in progress. It has the same O(n log n) time and gives the same answers. The event sweep needs no heap, only a sort.

Edge cases and common mistakes

No meetings. There are no events, the sweep does nothing and the method returns 0.
Touching meetings. [[1, 2], [2, 3]] needs one room, because at time 2 the end event comes before the start event.
Identical meetings. [[1, 5], [1, 5], [1, 5]] needs three rooms, since all three run at once.
One long meeting containing others. [[0, 10], [2, 3], [4, 5]] needs two rooms: the two short meetings never overlap each other, so they share the second room.
Wrong order for equal times. Putting start events before end events at the same time overcounts. The only line that decides this is the a.second < b.second comparison.
Only sorting by time. A comparison that looks only at first leaves events with equal times in an unspecified order, so the answer for touching meetings can come out wrong.
Returning the counter instead of the maximum. At the end of the sweep the counter is always 0.

Testing

[[5, 10], [0, 30], [15, 20]] gives 2.
[[1, 2], [2, 3]] gives 1.
[[1, 5], [1, 5], [1, 5]] gives 3.
[[0, 10], [2, 3], [4, 5]] gives 2.
[] gives 0.

Keep going with C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free