LESSON 320 OF 338 · GREEDY

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

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 and use O(1) extra space.

STEP 1 OF 6

Guided

Ctrl + Enter to check

Non Overlapping Intervals in Go, explained

Problem overview

The method nonOverlappingIntervals(intervals) receives a slice of intervals, each a two-element slice [start, end], and returns the largest number of them that can be chosen so that no two chosen intervals overlap. Intervals that only touch at an end point, such as [1, 2] and [2, 3], do not overlap. Each 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 side by side. [1, 3] overlaps the first two, so it would cost more than it gains. The statement asks for O(n log n) time and O(1) extra space.

Approach: always take the interval that ends first

A brute-force search would try every subset of intervals, which is exponential. A greedy rule does the job in one sort and one pass.

Sort the intervals by their end point and scan from left to right, taking an interval whenever it starts at or after the end of the last one taken. Why does this work? Among the intervals that are still available, the one that ends first leaves the most room for everything after it. Suppose some best answer does not contain it. Its first interval ends no earlier than ours, so swapping our earliest-ending interval in for that one keeps the selection free of overlaps and the same size. Repeating the argument at every step shows the greedy choice is never worse than any other.

Sorting by start point does not work. Take [[1, 10], [2, 3], [4, 5]]. Sorted by start, the first interval is the long [1, 10]; taking it blocks the other two and gives 1. Sorted by end, the order is [2, 3], [4, 5], [1, 10], and the scan takes two intervals, which is the best possible.

The sort costs O(n log n) and the scan is linear, so the total matches the statement's budget.

Step by step

Sort by end point with sort.Slice. Its second argument is a function of two indices i and j that returns whether the element at i must come before the element at j, here intervals[i][1] < intervals[j][1].
Take the first interval. After sorting, it ends earliest, so taking it is safe. Declare result as 1 and lastTaken as 0 in one statement. lastTaken is the index of the last chosen interval.
Scan the rest with i from 1 up to len(intervals) - 1.
Test for overlap. The current interval is compatible when its start, intervals[i][0], is at least the end of the last taken one, intervals[lastTaken][1]. The comparison is >= because touching intervals don't overlap.
Take it. Increment result and set lastTaken = i. Storing the index lets the next comparison read the end point.
Return result after the loop.

The solution in Go

type Solution struct {}

func (this Solution) nonOverlappingIntervals(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][1] < intervals[j][1]
    })
    result, lastTaken := 1, 0
    for i := 1; i < len(intervals); i++ {
        if intervals[i][0] >= intervals[lastTaken][1] {
            result++
            lastTaken = i
        }
    }
    return result
}

Go details worth a closer look:

sort.Slice comes from the sort package, which the file must import. It sorts the slice in place, so the caller's slice is reordered. For the first example it ends up as [[1 2] [2 3] [1 3] [3 4]] or with the two intervals ending at 3 swapped.
The comparison function takes indices, not elements. It reads intervals[i] and intervals[j] itself. Mixing up i and j in the body gives a wrong or inconsistent order.
sort.Slice is not stable. Intervals with equal end points may come out in either order. That's fine here: for equal ends, either one blocks the later intervals equally well, so the count is the same.
Method receivers. Go has no classes. Solution is a struct, and (this Solution) is the receiver. this is only a name Go lets you choose; it has no special meaning.
Multiple assignment with :=. result, lastTaken := 1, 0 declares both variables at once, and both are used.
result++ is a statement in Go, not an expression, so it can't be used inside a larger one.

Complexity

The sort takes O(n log n) time and the scan O(n), for O(n log n) overall. The solution makes no copy of the data; it reorders the input in place and keeps two integers. Apart from the small internal stack of the sorting routine, the extra space is O(1).

Edge cases and common mistakes

Touching intervals. Using > instead of >= would reject [1, 2] followed by [2, 3], and the first example would give 2 instead of 3.
Identical intervals. For [[1, 2], [1, 2], [1, 2]] only one can be taken. Each repeat starts at 1, before the first one ends at 2, so the answer is 1.
A single interval. The loop doesn't run and the answer is 1.
An empty slice. The code starts result at 1 without checking, so it would return 1 rather than 0. The problem assumes at least one interval; a guard at the top would handle the empty case.
Sorting by start point or by length. Both orders have counterexamples. The end point is what matters.
Comparing against the previous interval in the list. The comparison must be against the last interval taken, because skipped intervals don't constrain the next one.

Testing

The first example gives 3. The input [[1, 10], [2, 3], [4, 5]] gives 2, and [[1, 3], [2, 4], [3, 5]] gives 2 (the first and the third touch at 3).

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

Start learning free