LESSON 329 OF 348 · GREEDY

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

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

TYPESCRIPT · GREEDY

Non Overlapping Intervals in TypeScript, explained

Problem overview

The method nonOverlappingIntervals(intervals) receives a list of intervals, each a [start, end] pair, and returns the largest number of them that you can choose so that no two chosen intervals overlap. Intervals that only touch at an end point, such as [1, 2] and [2, 3], don't overlap. Each end is greater 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 together. The interval [1, 3] overlaps the first two, so taking it would cost you more than it gains.

The statement asks for O(n log n) time, which points to sorting followed by one linear pass.

Approach: always take the interval that ends first

Checking every subset of intervals takes exponential time. A greedy rule is much cheaper: sort the intervals by their end points, then walk through them and take each one that doesn't overlap the last interval you took.

Why does the earliest end work? Among all intervals, 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, so you can swap that interval for the earliest-ending one without creating a clash, and the count stays the same. So taking the earliest-ending interval is always safe, and the same argument applies again to what remains.

The sort key matters. Sorting by start doesn't work: with [[1, 10], [2, 3], [4, 5], [6, 7]], going by start takes [1, 10] first, which blocks everything else, and the count is 1. Going by end takes [2, 3], [4, 5] and [6, 7] for a count of 3.

Trace of the first example. After sorting by end, the order is [1, 2], [2, 3], [1, 3], [3, 4]. Take [1, 2]. Next, [2, 3] starts at 2, which is at least the last end (2), so take it. [1, 3] starts at 1, before the last end (3), so skip it. [3, 4] starts at 3, so take it. The total is 3.

Step by step

Sort by end point. The starter code already does this with a comparator on [1].
Take the first interval. After the sort it ends earliest, so it is always safe. Set result to 1.
Remember the last taken interval. lastTaken holds its index, 0 at first. Both variables are declared in one let statement.
Loop over the rest, from index 1.
Compare start with the last end. If intervals[i][0] is greater than or equal to intervals[lastTaken][1], the two don't overlap. Use >=, so touching intervals count as compatible.
Take it. Increment result and set lastTaken to i. Storing the index lets the next comparison read the end.
Return result after the loop.

The solution in TypeScript

class Solution {
    nonOverlappingIntervals(intervals: number[][]): number {
        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;
    }
}

TypeScript details worth knowing:

Always pass a comparator to sort. Without one, sort converts elements to strings and compares them as text, so [10, 9, 1].sort() gives [1, 10, 9]. Intervals would be compared as strings like "1,2", which is not what we want.
The comparator returns a number. Negative means the first argument goes first, positive means the second goes first, and 0 means a tie. Subtracting the end points gives exactly that for ordinary numbers.
sort changes the array in place. After the call, the caller's intervals are reordered: [[1, 2], [2, 3], [3, 4], [1, 3]] becomes [[1, 2], [2, 3], [1, 3], [3, 4]]. Sort a copy, [...intervals], if the order matters elsewhere.
The sort is stable. Intervals with equal ends keep their original relative order. Here it makes no difference to the answer.
One let, two variables. let result = 1, lastTaken = 0; declares both. TypeScript infers number for each.
Types are erased. number[][] documents and checks what you pass in, but nothing is verified at run time.

Complexity

Time: O(n log n). Sorting costs O(n log n) comparisons and the pass after it costs O(n).

Space: O(1) beyond the input. The loop uses two integers and sorts in place. The engine's sort may use scratch memory internally, but the code allocates no array of its own.

Edge cases and common mistakes

Touching intervals. [[1, 2], [2, 3]] returns 2. Using > instead of >= would return 1.
One interval. [[1, 5]] returns 1.
Identical intervals. [[1, 2], [1, 2]] returns 1, because they overlap completely.
Nested intervals. [[1, 10], [2, 3], [4, 5], [6, 7]] returns 3: the long interval is skipped because the short ones end first.
Empty input. The function starts result at 1 and so returns 1 for [], although the right answer is 0. The lesson doesn't ask for this case, but a robust version would return 0 for an empty list before sorting.
Sorting by start. As shown above, it gives wrong answers on nested intervals.
Comparing with the previous interval instead of the last taken one. A skipped interval must not become the reference point.

Testing

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

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

Start learning free