LESSON 354 OF 415 · GREEDY

Non Overlapping Intervals in Swift: 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. Apart from the sorting, the greedy pass needs only O(1) extra space.

STEP 1 OF 6

Guided

Ctrl + Enter to check

SWIFT · GREEDY

Non Overlapping Intervals in Swift, explained

Problem overview

The method nonOverlappingIntervals(_ intervals: [[Int]]) receives intervals written as [start, end] and returns the largest number of them that can be chosen so that no two overlap. Intervals that only touch at an endpoint, 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: [1, 2], [2, 3] and [3, 4]. The statement asks for O(n log n) time.

Approach: always take the interval that ends first

Checking every subset of intervals is exponential. A greedy rule is much faster: sort the intervals by end point, then walk through them and take each one that starts at or after the end of the last one taken.

Why does it work? Among all intervals, the one with the smallest end leaves the most room to the right. Suppose some best answer does not contain it. Replace that answer's first interval by this one. The replacement ends no later, so it still fits before the second interval, and the count is unchanged. So there is always a best answer that takes the earliest-ending interval, and after taking it the same argument applies to the intervals that start at or after its end.

Trace the example. Sorted by end, the list is [1, 2], then the two intervals ending at 3 (in either order), then [3, 4]:

Take [1, 2] as the first one. The last end is 2.
[2, 3] starts at 2, which is not before 2, so take it. The last end is 3.
[1, 3] starts at 1, which is before 3, so skip it.
[3, 4] starts at 3, so take it.

Three intervals are taken. Intervals that tie on their end point make no difference to the count.

Step by step

Sort by end point. The starter code already has var intervals = intervals, a mutable copy. sort with the trailing closure { $0[1] < $1[1] } orders the intervals by their second element.
Take the first interval. It ends the earliest, so taking it is safe. Declare result = 1 and lastTaken = 0 in a single var declaration.
Loop over the rest with stride(from: 1, to: intervals.count, by: 1).
Check for overlap. The current interval is compatible when its start, intervals[i][0], is greater than or equal to the end of the last taken one, intervals[lastTaken][1]. Use >=, because touching is allowed.
Take it. Add one to result and set lastTaken to i. Storing the index lets the next comparison read the end point.
Return result after the loop.

The solution in Swift

class Solution {
    func nonOverlappingIntervals(_ intervals: [[Int]]) -> Int {
        var intervals = intervals
        intervals.sort { $0[1] < $1[1] }
        var result = 1, lastTaken = 0
        for i in stride(from: 1, to: intervals.count, by: 1) {
            if intervals[i][0] >= intervals[lastTaken][1] {
                result += 1
                lastTaken = i
            }
        }
        return result
    }
}

Swift details worth knowing:

Sorting with a closure. sort reorders the array in place and takes a closure that says whether its first argument should come before the second. $0 and $1 are the two intervals, and $0[1] < $1[1] compares their end points. The array's sort is not guaranteed to keep equal elements in order, which is fine here.
sort and sorted. sort changes the array it is called on, so it needs a var. sorted returns a new array and works on a let.
stride instead of a range. 1..<intervals.count would crash for an empty list, because the lower bound 1 is above the upper bound 0. stride(from:to:by:) just produces no values in that case, so the loop is skipped.
Several variables in one var. var result = 1, lastTaken = 0 declares two separate variables, both inferred as Int.
The copy. The caller's array is not changed, because intervals is a copy. That copy is made when sort first writes to it, so it uses extra memory of size O(n).

Complexity

Time: O(n log n). The sort dominates, and the scan afterwards is one pass of O(n).

Space. The scan uses a few integers. The sort works on the copy of the list, so the method as written holds a second array of n elements. An inout parameter would let the method sort the caller's array in place, but this signature takes the array by value, so the copy is part of the design and keeps the input unchanged.

Edge cases and common mistakes

Touching intervals. [[1, 2], [2, 3]] gives 2. Using > instead of >= would give 1.
Identical intervals. [[1, 2], [1, 2], [1, 2]] gives 1: the second and third start before the first one ends.
A long interval covering short ones. [[1, 5], [2, 3], [4, 6]] gives 2: take [2, 3] and [4, 6]. Sorting by start and taking the first would pick [1, 5] and lose.
One interval. [[1, 10]] gives 1.
Empty input. The loop is skipped, but result starts at 1, so this version returns 1 for an empty list. Real use would need a guard that returns 0 first.
Comparing with the wrong end. The start must be compared with the end of the last taken interval, not with the end of the previous interval in the sorted list.

Testing

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

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

Start learning free