Start learning free

LESSON 349 OF 410 · GREEDY

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

  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

    JAVASCRIPT · GREEDY

    Non Overlapping Intervals in JavaScript, explained

    Problem overview

    The method nonOverlappingIntervals(intervals) receives an array of [start, end] pairs and returns the largest number of them that can be chosen so that no two chosen intervals overlap. Intervals that only touch, such as [1, 2] and [2, 3], do not overlap. Every interval ends after it starts.

    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] would collide with the first two. This is the classic activity selection problem: given many bookings, fit in as many as possible.

    The lesson asks for O(n log n) time and O(1) extra space.

    The method counts the intervals to keep. If you need the number of intervals to remove so that the rest do not overlap, compute intervals.length - result; here that is 4 - 3 = 1.

    Approach: always take the interval that ends first

    Trying every subset of intervals is exponential, so the problem needs a rule that makes the choice for us. A greedy rule is a good fit: pick the interval that leaves the most room for the ones after it. That is the interval with the smallest end point.

    Sorting by end point and scanning from left to right applies this rule over and over. The first interval after sorting ends earliest, so taking it is always safe: any solution that uses a different first interval can swap it for this one, because this one ends no later, and the swap does not create an overlap. After taking it, the same argument applies to the intervals that start at or after its end.

    The rule needs the sort to be by end point. Sorting by start point fails. For [[1,10],[2,3],[4,5],[6,7]] a start-ordered scan takes [1,10] first and then everything else overlaps it, so the result is 1. Sorted by end, the order is [2,3], [4,5], [6,7], [1,10], and the scan takes the first three and returns 3.

    Step by step

    1. Sort by end point. The comparator receives two intervals, first and second, and returns first[1] - second[1]. A negative result puts first before second. Without a comparator, JavaScript would compare the intervals as strings.
    2. Take the first interval. Set result = 1 and lastTaken = 0. Both are declared with a single let. The interval with the earliest end is always safe to take.
    3. Loop from index 1. Index 0 is already chosen, so the loop starts at 1 and runs while i < intervals.length.
    4. Test for overlap. The current interval fits if its start, intervals[i][0], is at least the end of the last taken one, intervals[lastTaken][1]. The comparison is >=, not >, because an interval starting exactly where the last one ended does not overlap it.
    5. Take it. Increment result and set lastTaken = i. The code stores the index rather than the interval so the next comparison can read its end point.
    6. Return result after the loop, once every interval has been considered.

    The solution in JavaScript

    class Solution {
    
    nonOverlappingIntervals(intervals) {
        intervals.sort((first, second) => (first[1] - second[1]));
        let result = 1, lastTaken = 0;
        for (let i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= intervals[lastTaken][1]) {
                result++;
                lastTaken = i;
            }
        }
        return result;
    }
}

    Trace for [[1,2],[2,3],[3,4],[1,3]]. After sorting by end, the array is [[1,2],[2,3],[1,3],[3,4]]. The scan takes [1,2] first. Then [2,3] starts at 2, which is at least 2, so it is taken. [1,3] starts at 1, which is less than 3, so it is skipped. [3,4] starts at 3, which is at least 3, so it is taken. The result is 3.

    JavaScript details

    • sort changes the caller's array. After the call, intervals is in end order. To keep the original order, sort a copy with [...intervals].sort(...); that costs O(n) extra space.
    • Intervals with equal ends. The comparator returns 0 for them, and since Node 11 sort is stable, so they keep their original relative order. Their order does not change the answer: once one of them is taken, the others overlap it or are skipped for the same reason.
    • The comparator must return a number. Returning first[1] > second[1], a boolean, does not sort correctly: false becomes 0, which tells sort the two intervals are equal.
    • The comma in let result = 1, lastTaken = 0; declares two variables in one statement. It is not the comma operator.

    Complexity

    • Time: O(n log n). The sort costs O(n log n) and the loop is one pass of O(n).
    • Space: O(1). The scan uses a few numbers. The lesson counts the sort as in place, though an engine may use temporary memory internally.

    Edge cases and common mistakes

    • Touching intervals. [[1,2],[2,3]] gives 2. Using > instead of >= would wrongly give 1.
    • Identical intervals. [[1,2],[1,2],[1,2]] gives 1, because only one of them can be chosen.
    • One interval. [[1,5]] returns 1, and the loop body never runs.
    • An empty array. The code assumes at least one interval, because it takes intervals[0] without looking. With an empty array it returns 1. If empty input is possible, return 0 first.
    • Sorting by start point. It looks natural and fails, as the [1,10] example above shows.
    • Comparing with the previous interval instead of the last taken one. A skipped interval must not become the reference point. Only the end of the last interval that was actually taken matters, which is why the code tracks lastTaken.

    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,5]] gives 1.
    Keep going with JavaScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free