LESSON 353 OF 414 · GREEDY

Non Overlapping Intervals in Rust: Greedy by End Point, O(n log n)

Practice O(n log n) Read the full explanation

Given a collection of intervals, find the maximum number of non-overlapping intervals you can select.

Example 1:

Input: [[1,2],[2,3],[3,4],[1,3]]
Output: 3
Explanation: [1,2], [2, 3] and [3, 4] are non-overlapping.

Note:

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

Your algorithm should run in O(n log n) time. Apart from the sorting, the greedy pass needs only O(1) extra space.

STEP 1 OF 6

Guided

Ctrl + Enter to check

RUST · GREEDY

Non Overlapping Intervals in Rust, explained

Problem overview

The function non_overlapping_intervals receives a vector of intervals, each a two-element vector [start, end], and returns the largest number of intervals you can keep so that no two of them overlap. Two intervals whose borders only touch, such as [1, 2] and [2, 3], don't overlap. Each interval's end is larger than its start.

For [[1, 2], [2, 3], [3, 4], [1, 3]] the answer is 3: the intervals [1, 2], [2, 3] and [3, 4] fit together, and [1, 3] overlaps two of them.

Approach: always take the interval that ends first

Trying every subset of intervals is exponential. A greedy rule is much faster: sort the intervals by their end point and walk through them, keeping an interval whenever it starts at or after the end of the last one you kept.

The rule works because the interval that ends earliest leaves the most room for everything after it. Suppose some best answer does not contain the earliest-ending interval, A. Its first interval, B, ends no earlier than A does, so replacing B with A cannot cause a new overlap with the rest, and the count stays the same. So some best answer always includes A. After taking it, the same argument applies to the intervals that start at or after A ends.

The statement sets O(n log n) time, which the sort provides. The walk afterwards is a single pass.

On the example, sorting by end gives [1, 2], [2, 3] and [1, 3] (in either order for the two intervals ending at 3), then [3, 4]. Take [1, 2]. Next, [2, 3] starts at 2, which is not before 2, so take it. [1, 3] starts at 1, before 3, so skip it. [3, 4] starts at 3, so take it. The count is 3.

Step by step

Start from the sorted vector. The starter code already calls sort_by_key with the end point as the key. The first interval after sorting ends earliest, so taking it is always safe.
Count it. Declare result as a mutable i32 starting at 1, for that first interval.
Remember the last kept interval. Declare last_taken as a mutable usize, starting at 0, because it will index the vector.
Walk the rest. Loop i over 1..intervals.len(). Index 0 is already taken.
Test for overlap. The current interval's start, intervals[i][0], must be greater than or equal to the end of the last kept one, intervals[last_taken][1]. Use >= because touching borders are allowed.
Keep it. Add 1 to result and set last_taken to i.
Return result after the loop.

The solution in Rust

impl Solution {
    fn non_overlapping_intervals(mut intervals: Vec<Vec<i32>>) -> i32 {
        intervals.sort_by_key(|a| a[1]);
        let mut result = 1i32;
        let mut last_taken = 0usize;
        for i in 1..intervals.len() {
            if intervals[i][0] >= intervals[last_taken][1] {
                result += 1;
                last_taken = i;
            }
        }
        result
    }
}

The Rust details worth knowing:

mut in the parameter. mut intervals makes the owned vector mutable inside the function, which sort_by_key requires since it reorders the elements in place. The caller's variable was moved into the function, so nothing outside changes.
The closure. |a| a[1] receives a reference to each inner vector and returns the key to sort by, here the end point. The key is an i32, which implements Ord. The sort compares keys and leaves the intervals themselves intact.
Stable sorting. sort_by_key keeps intervals with equal keys in their original order. The greedy walk doesn't depend on that, since intervals with the same end are interchangeable for the count.
Typed literals. 1i32 fixes the result type to match the return type, and 0usize makes last_taken usable as an index. Vectors accept only usize indexes.
No ++. Rust has no increment operator, so the count goes up with += 1.
Tail expression. result without a semicolon is the function's value.

Complexity

Time: O(n log n). The sort costs O(n log n), and the pass afterwards is O(n).

Space: close to O(1) beyond the input, with a caveat. The walk uses only two variables, but sort_by_key is a stable sort, and stable sorting in Rust may allocate a temporary buffer that grows with the input. If you need a strict constant-space sort, sort_unstable_by_key sorts in place and gives the same answer here, because the order of intervals with equal ends doesn't affect the count.

Edge cases and common mistakes

Touching intervals. [[1, 2], [2, 3]] gives 2. With > instead of >= the answer would be 1.
Identical intervals. [[1, 2], [1, 2], [1, 2]] gives 1, since only one can be kept.
One long interval around short ones. [[1, 10], [2, 3], [4, 5]] gives 2. The long interval ends last, so it is considered last and skipped.
Sorting by start instead of end. The long interval [1, 10] would be taken first and block everything else, giving 1.
A single interval. The loop is empty and the function returns 1.
An empty vector. The function returns 1, because result starts at 1 and never checks. The lesson's inputs always hold at least one interval, but a general-purpose function would return 0 early for an empty input.
Comparing with the wrong interval. The start must be compared with the end of the last kept interval, not the one just before it in the vector.

Testing

[[1,2],[2,3],[3,4],[1,3]] gives 3.
[[1,2],[1,2],[1,2]] gives 1.
[[1,10],[2,3],[4,5]] gives 2.
[[1,2]] gives 1.

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

Start learning free