LESSON 354 OF 414 · GREEDY

Meeting Rooms II in Rust: Minimum Rooms in O(n log n) With 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

RUST · GREEDY

Meeting Rooms in Rust, explained

Problem overview

The function meeting_rooms receives a vector of meetings, each a two-element vector [start, end], and returns the smallest number of rooms that lets every meeting happen. A meeting that ends at the moment another starts doesn't overlap it, so [1, 2] and [2, 3] can share a room. Each end is larger than its start.

For [[5, 10], [0, 30], [15, 20]] the answer is 2. The meetings [5, 10] and [15, 20] can use one room, one after the other, while [0, 30] runs the whole time and needs its own.

Approach: sweep through start and end events

The number of rooms needed equals the largest number of meetings that are running at the same moment. Finding that peak by comparing every pair of meetings is slow. A cleaner way is to look at the timeline instead of at the meetings.

Turn each meeting into two events: a start at its start time that adds one running meeting, and an end at its end time that removes one. Sort all events by time and sweep through them, keeping a counter of meetings in progress. After every event, compare the counter with the best value so far. The best value is the answer.

One detail decides correctness: what to do with events at the same time. When one meeting ends exactly as another begins, the room is free in time for the new one. So at equal times, end events must come before start events. Giving an end the value -1 and a start the value 1, sorting by time and then by that value does exactly this, and the same value can be added to the counter.

On the example the events are (0, start), (5, start), (10, end), (15, start), (20, end), (30, end). The counter goes 1, 2, 1, 2, 1, 0. Its peak is 2.

The sort makes the time O(n log n) and the event list needs O(n) space, matching the statement's limits.

Step by step

Create the event list. events is a mutable Vec<(i32, i32)> made with Vec::new(). Each event is a tuple of a time and a type. The annotation tells Rust what the empty vector will hold.
Loop over the meetings with for interval in &intervals. Iterating over a reference borrows the vector rather than moving it.
Push the start event. (interval[0], 1): the start time, tagged 1.
Push the end event. (interval[1], -1): the end time, tagged -1.
Sort the events with sort_by and a closure. If the times are equal, compare the types, so -1 comes before 1. Otherwise compare the times.
Declare the counters. answer holds the largest count so far and no_of_meetings the current count, both i32 and both starting at 0.
Sweep. Loop over &events with the pattern (_, event_type), ignoring the time.
Update the count. Add event_type to no_of_meetings. That is why the types are 1 and -1.
Track the peak with answer = answer.max(no_of_meetings).
Return answer.

The solution in Rust

impl Solution {
    fn meeting_rooms(intervals: Vec<Vec<i32>>) -> i32 {
        let mut events: Vec<(i32, i32)> = Vec::new();
        for interval in &intervals {
            events.push((interval[0], 1));
            events.push((interval[1], -1));
        }
        events.sort_by(|a, b| {
            if a.0 == b.0 {
                a.1.cmp(&b.1)
            } else {
                a.0.cmp(&b.0)
            }
        });
        let mut answer = 0i32;
        let mut no_of_meetings = 0i32;
        for (_, event_type) in &events {
            no_of_meetings += event_type;
            answer = answer.max(no_of_meetings);
        }
        answer
    }
}

The Rust details worth knowing:

Tuples. (i32, i32) groups two values, read by position as .0 and .1. The first is the time and the second the type.
Borrowing in for loops. for interval in &intervals yields &Vec<i32> references and leaves intervals usable afterwards. Without the & the loop would consume the vector. Inside, interval[0] copies an i32 out of it.
The comparator. sort_by takes a closure receiving two references and returning an Ordering: Less, Equal or Greater. cmp takes a reference to the other value, hence &b.1. Both branches of the if produce an Ordering, and since neither ends with a semicolon, the chosen one is the closure's value.
Destructuring a reference. Looping over &events gives &(i32, i32). The pattern (_, event_type) matches through the reference, ignores the time with _, and binds event_type as a &i32.
+= with a reference. Rust implements i32 += &i32, so no_of_meetings += event_type compiles without writing *event_type.
Typed literals. 0i32 fixes the type with no separate annotation.

Complexity

Time: O(n log n). Building the events is O(n). Sorting 2n events costs O(n log n), and the sweep is O(n).

Space: O(n). The list holds two tuples per meeting.

Edge cases and common mistakes

Back-to-back meetings. [[1, 2], [2, 3]] needs 1 room. At time 2 the end (-1) sorts before the start (1), so the count drops to 0 before rising again. If starts came first, the count would reach 2.
Everything overlapping. [[0, 5], [1, 6], [2, 7]] needs 3 rooms.
A single meeting. The answer is 1.
No meetings. An empty vector gives no events, and the function returns 0.
Sorting by time only. A comparator that ignores the type leaves equal times in whatever order the events were pushed. For [[2, 3], [1, 2]] the start at time 2 is pushed before the end at time 2, so the count briefly reaches 2 and the answer is wrong. The tie-break on the type is what prevents it.
Taking the last count instead of the peak. The counter ends at 0, so the answer has to be the maximum seen along the way.

Testing

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

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

Start learning free