LESSON 329 OF 348 · GREEDY

Non Overlapping Intervals in Kotlin: O(n log n) Greedy by End Time

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 Kotlin, explained

Problem overview

The function nonOverlappingIntervals(intervals) receives an Array<IntArray> where each IntArray is a pair [start, end]. It returns the largest number of intervals you can select so that no two of them overlap. Intervals that only touch at an end point, like [1, 2] and [2, 3], do not overlap. Each interval's 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] fit side by side, while [1, 3] overlaps two of them. The statement asks for O(n log n) time.

Approach: always take the interval that ends first

Checking every subset of intervals takes exponential time. A greedy rule finds the best selection with one sort and one pass. Sort the intervals by their end points. The interval that ends earliest leaves the most room for everything after it, so taking it never hurts: any best selection can swap its first interval for the earliest-ending one without creating an overlap. After taking it, repeat the argument on the intervals that start at or after its end.

In practice this is a single scan. Keep the last interval you took. For each next interval in sorted order, if its start is at least the last taken end, it doesn't overlap, so take it. Otherwise skip it. Sorting by end is the key detail: sorting by start would let a long interval block many short ones.

On the example, sorting by end gives [1, 2], [2, 3] and [1, 3] (the sort is stable, so ties keep their original order), then [3, 4]. Take [1, 2]. [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.

Why the greedy choice is safe: suppose some best selection starts with a different interval X. The earliest-ending interval E ends no later than X does, so replacing X by E cannot create a clash with the intervals that come after X. The selection keeps its size, so a best selection containing E always exists.

Step by step

Sort by end point. The starter code already does this with intervals.sortBy { it[1] }, which orders the array in place by each pair's second value.
Take the first interval. After sorting it ends earliest, so taking it is always safe. Start result as a var at 1.
Remember the last taken interval. Keep its index in a var lastTaken, initially 0, so the next comparison can read intervals[lastTaken][1].
Loop i from 1 until intervals.size. Index 0 is already in the answer.
Test for overlap. The interval at i is compatible when intervals[i][0] >= intervals[lastTaken][1]. The comparison is >= because touching intervals don't overlap.
Take it. Increment result and set lastTaken to i.
Return result after the loop.

The solution in Kotlin

class Solution {
    fun nonOverlappingIntervals(intervals: Array<IntArray>): Int {
        intervals.sortBy { it[1] }
        var result = 1
        var lastTaken = 0
        for (i in 1 until intervals.size) {
            if (intervals[i][0] >= intervals[lastTaken][1]) {
                result++
                lastTaken = i
            }
        }
        return result
    }
}

The Kotlin details worth a closer look:

sortBy { it[1] }. It sorts an Array in place using the value the lambda returns for each element as the sort key. Here it is one IntArray pair and it[1] is its end. The sort is stable, so intervals with equal ends keep their original relative order. Calling sortBy changes the caller's array: after sorting [[1, 3], [2, 3], [1, 2]] it reads [[1, 2], [1, 3], [2, 3]].
sortBy versus sortedBy. sortBy on an array sorts that array. sortedBy returns a new list and leaves the array alone.
var for values that change. result and lastTaken are reassigned inside the loop, so they can't be val.
result++. Kotlin has the same increment operator as Java, and here it is used as a statement.
until. 1 until intervals.size stops at the last index, so no read goes out of range.

Complexity

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

Space: O(1) beyond the sort. The scan keeps two integers. The array is sorted in place, although the library's sort may use temporary memory of its own while it runs.

Edge cases and common mistakes

Touching intervals. [[1, 2], [2, 3]] returns 2. With > instead of >= the result would be 1.
Identical intervals. [[1, 2], [1, 2], [1, 2]] returns 1: only one copy can be chosen.
One long interval covering short ones. [[1, 10], [2, 3], [4, 5]] returns 2, because the two short intervals beat the long one. Sorting by start would pick the long one first and answer 1.
A single interval. [[1, 3]] returns 1.
An empty array. The code starts result at 1, so an empty array returns 1 instead of 0. The statement doesn't say the input is non-empty; if it could be, return 0 first when intervals.isEmpty().
Comparing with the previous interval instead of the last taken. A skipped interval must not become the reference. Always compare with intervals[lastTaken].
Sorting by the wrong key. it[0] sorts by start and breaks the greedy argument.

Testing

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

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

Start learning free