Start learning free

LESSON 353 OF 414 · GREEDY

Non Overlapping Intervals in Scala: 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:

  1. You may assume the interval's end point is always bigger than its start point.
  2. 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
    Ctrl + Enter to check

    SCALA · GREEDY

    Non Overlapping Intervals in Scala, explained

    Problem overview

    The method nonOverlappingIntervals(intervals) receives an array of intervals, each an array [start, end], and returns the largest number of them that can be chosen so that no two overlap. Every end is greater than its start, and intervals that only touch, such as [1, 2] and [2, 3], don't overlap.

    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. The statement asks for O(n log n) time, which the sort provides.

    Approach: always take the interval that ends first

    Checking every subset of intervals would be exponential. A greedy rule is enough: sort by end point, take the first interval, and then take each later interval that starts no earlier than the last taken one ends.

    The reason is an exchange argument. Among all intervals, the one that ends first leaves the most room to its right. Any best selection can swap its first interval for the earliest-ending one without creating an overlap, because that interval ends no later than the one it replaces. The same argument then applies to what is left. So taking the earliest end each time never costs a place in the answer.

    Here is the example. Sorted by end, [1, 2] comes first, then [2, 3] and [1, 3] (both end at 3, in either order), then [3, 4]. The interval [1, 2] is taken. [2, 3] starts at 2, which is at least the last taken end (2), so it is taken. [1, 3] starts at 1, before the last taken end, so it is skipped, whichever of the two ends-at-3 intervals is checked first. [3, 4] starts at 3, the end of [2, 3], so it is taken. The count is 3.

    Step by step

    1. The starting code sorts the intervals by their end points into sorted. Sorting is what makes the greedy choice valid.
    2. Take the first interval by declaring result as a var set to 1. It changes inside the loop, so it can't be a val.
    3. Remember the last taken interval as the index lastTaken, a var starting at 0. Keeping the index lets you read its end point on each comparison.
    4. Loop over the rest with 1 until sorted.length. Index 0 is already taken. The loop reads from sorted, because the original array is not sorted.
    5. Test for overlap: the current start sorted(i)(0) must be at least sorted(lastTaken)(1). The comparison is >= because an interval that starts exactly where the last one ends doesn't overlap it.
    6. Take it: add 1 to result and set lastTaken to i.
    7. Return result after the loop.

    The solution in Scala

    class Solution {
    def nonOverlappingIntervals(intervals: Array[Array[Int]]): Int = {
        val sorted = intervals.sortBy(_(1))
        var result = 1
        var lastTaken = 0
        for (i <- 1 until sorted.length) {
            if (sorted(i)(0) >= sorted(lastTaken)(1)) {
                result += 1
                lastTaken = i
            }
        }
        result
    }
}

    Some Scala details in this code:

    • sortBy(_(1)) sorts by a key taken from each element. The underscore stands for the element, so _(1) means "element at index 1", the end point. It is shorthand for x => x(1). The keys are Ints, so they sort in ascending order.
    • sortBy returns a new array. The array passed in stays in its original order. That is why the loop uses sorted and not intervals.
    • Two sets of parentheses to index. sorted(i)(0) first gets interval i, then its start. Arrays use parentheses in Scala, not square brackets.
    • No ++ operator. Scala has no result++, so the code writes result += 1.
    • var against val. Both counters are reassigned, so they are var. sorted never changes, so it is a val.
    • The last expression is the result. The final line, result, is the method's value without return.

    Complexity

    Time: O(n log n). The sort dominates. The loop that follows is a single pass of O(n).

    Space: O(n) for this code. sortBy builds a new array of the intervals' references, so it needs memory proportional to n. A solution that sorted the input in place would use O(1) extra space apart from the sort's own working memory. The loop itself uses only two integers.

    Edge cases and common mistakes

    • Touching intervals. Using > instead of >= would reject [1, 2] followed by [2, 3], and the example would give 2 instead of 3.
    • Sorting by start. A long interval such as [1, 10] would be taken first and block the short ones inside it. For [[1, 10], [2, 3], [4, 5], [6, 7]] sorting by end gives 3, taking the three short intervals.
    • Identical intervals. [[1, 2], [1, 2], [1, 2]] gives 1: after the first is taken, the others start before its end.
    • Chained overlaps. For [[1, 3], [2, 4], [3, 5]] the answer is 2: the first and third fit together, and the middle one overlaps both.
    • A single interval. The loop doesn't run, and the answer is 1.
    • An empty array. The method returns 1, because result starts at 1 without checking that an interval exists. The statement doesn't promise a non-empty input, so a robust version would return 0 first.
    • Comparing with the wrong interval. The start must be compared with the end of the last taken interval, not of the previous interval in the sorted order. That is why lastTaken exists.
    • Reading intervals in the loop. The original array is not sorted, so the comparison would use the wrong order.

    Testing

    • [[1, 2], [2, 3], [3, 4], [1, 3]] gives 3.
    • [[1, 10], [2, 3], [4, 5], [6, 7]] gives 3.
    • [[1, 2], [1, 2], [1, 2]] gives 1.
    • [[1, 3], [2, 4], [3, 5]] gives 2.
    • [[1, 5]] gives 1.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free