Non-overlapping Intervals

The problem

You are given a list intervals of n intervals [start, end] (n is the length of intervals). Return the fewest intervals you must remove so that the ones left do not overlap.

Here, intervals that only touch do not overlap: [1, 3] and [3, 5] can both stay.

Example 1

Input: intervals = [[1, 4], [2, 3], [3, 6], [5, 7], [6, 8]]

Output: 2

Remove [1, 4] and [5, 7]. The rest, [2, 3], [3, 6] and [6, 8], only touch. No way keeps 4.

intervals

remove

[1, 4][5, 7]

Example 2

Input: intervals = [[1, 5], [1, 5], [1, 5]]

Output: 2

Three copies of the same interval. Only one can stay.

Example 3

Input: intervals = [[0, 2], [2, 4]]

Output: 0

They touch at 2, which is allowed.

Constraints

• 1 ≤ n ≤ 100,000
• −50,000 ≤ start < end ≤ 50,000

Clarifying questions

Do touching intervals overlap?

No, not here. [1, 3] and [3, 5] may both stay. That is the opposite of Merge Intervals.

Do we return the count or the intervals?

Only the count of intervals to remove.

Is the input sorted?

No. Sorting is our job.

Can intervals repeat?

Yes. Exact copies overlap each other, so all but one must go.

Spot the pattern

Removing the fewest is the same as keeping the most intervals with no overlap. That is a scheduling question: fit as many meetings as possible into one room. The classic answer is greedy: always keep the interval that ends first. Sorting by end makes that one pass.

Solutions

Longest chainO(n²)Greedy by endO(n log n)

Show all

Trying every subset of intervals is O(2ⁿ). The table below is the same search with each result stored once.

Longest chain O(n²)

The idea

Sort by start. Then build a table: keep[i] is the most intervals we can keep, with no overlap, if interval i is the last one kept.

To fill keep[i], look at every interval j before it. If j ends by the time i starts, then i can follow the best chain that ends at j, giving keep[j] + 1. Take the best such j. The answer is n minus the largest value in the table.

It tries every way to chain the intervals, so it is correct. But each interval looks back at all the ones before it.

Walkthrough

intervals

keep

·0·1·2·3·4

1. intervals.sort(key=lambda interval: interval[0])
2. keep = [1] * len(intervals)
3. for i in range(len(intervals)):
4. for j in range(i):
5. if intervals[j][1] <= intervals[i][0]:
6. keep[i] = max(keep[i], keep[j] + 1)
7. return len(intervals) - max(keep)

Sort by start, so every interval that can come before interval i sits to its left.

← BackStep →Play1 / 8

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Longest chain: keep[i] is the most intervals we can keep if interval i is
    // the last one kept. Each interval looks back at all others: O(n^2) time, O(n) memory.
    public int eraseOverlapIntervals(int[][] intervals) {
        // Sorted by start, every interval that can come before i sits to its left.
        java.util.Arrays.sort(intervals, (first, second) -> Integer.compare(first[0], second[0]));
        int intervalsLength = intervals.length, best = 0;
        int[] keep = new int[intervalsLength];
        for (int i = 0; i < intervalsLength; i++) {
            keep[i] = 1;
            for (int j = 0; j < i; j++) {
                // <=: touching is allowed, so j may end exactly where i starts.
                if (intervals[j][1] <= intervals[i][0]) keep[i] = Math.max(keep[i], keep[j] + 1);
            }
            best = Math.max(best, keep[i]);
        }
        // Removing the fewest is keeping the most.
        return intervalsLength - best;
    }
}

Big O

Time O(n²)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The lit lines compare two intervals and maybe update keep[i]. They sit inside two loops. That is 1 step per run. The sort before them costs n log n.

   1. intervals.sort(key=lambda interval: interval[0])
   2. keep = [1] * len(intervals)
   3. for i in range(len(intervals)):
   4. for j in range(i):
   5. if intervals[j][1] <= intervals[i][0]:
   6. keep[i] = max(keep[i], keep[j] + 1)
   7. return len(intervals) - max(keep)

2. 2 Count the runs on Example 1

   Example 1 has 5 intervals. Interval 0 looks back at none, interval 1 at 1, and so on up to interval 4, which looks back at 4.

   0 + 1 + 2 + 3 + 4 = 10 checks, plus the sort.

   i	0	1	2	3	4
   pairs checked	0	1	2	3	4

   total

   0 + 1 + 2 + 3 + 4 = 10, plus the sort

3. 3 Write the count for any n

   0 + 1 + … + (n − 1) = n × (n − 1) / 2, plus n log₂ n for the sort

   Check it with Example 1: 5 × 4 / 2 = 10.

4. 4 Keep only the part that grows fastest

   Keep the n². It grows faster than the sort’s n log n, so the sort is the smaller part here. Drop the ½ too. What is left is n².

   So the time is O(n²).

5. S Space: count the extra memory the same way

   The keep table holds one number per interval, so the space is O(n).

   keep (n numbers)ij

Greedy by end O(n log n)

The idea

Sort by end. Walk the intervals in that order and keep track of last_end, where the last kept interval ends.

• If an interval starts at or after last_end, it fits. Keep it, and move last_end to its end.
• If it starts before last_end, it overlaps the last kept one. Remove it, and count it.

Why it is correct: of all intervals that could come next, the one that ends first leaves the most room for the rest. Swapping it in for any other choice never makes things worse. So greedily keeping the earliest end keeps the most intervals, and removes the fewest.

Walkthrough

intervals

last_end

−∞

removed

0

1. intervals.sort(key=lambda interval: interval[1])
2. removed, last_end = 0, -inf
3. for start, end in intervals:
4. if start >= last_end:
5. last_end = end
6. else:
7. removed += 1
8. return removed

To keep as many as we can, we want each kept interval to end as early as possible. That leaves the most room for the rest.

← BackStep →Play1 / 8

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Greedy by end: always keep the interval that ends first, because it leaves
    // the most room. The sort costs O(n log n), the loop O(n).
    public int eraseOverlapIntervals(int[][] intervals) {
        java.util.Arrays.sort(intervals, (first, second) -> Integer.compare(first[1], second[1]));
        int removed = 0;
        long lastEnd = Long.MIN_VALUE;
        for (int[] interval : intervals) {
            // >=: touching is allowed, so it may start exactly where the last one ends.
            if (interval[0] >= lastEnd) lastEnd = interval[1];
            // It overlaps a kept interval that ends sooner, so this one goes.
            else removed++;
        }
        return removed;
    }
}

Big O

Time O(n log n)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Two parts repeat. The sort compares intervals many times. Then the loop does one comparison per interval, which is 1 step per run.

   1. intervals.sort(key=lambda interval: interval[1])
   2. removed, last_end = 0, -inf
   3. for start, end in intervals:
   4. if start >= last_end:
   5. last_end = end
   6. else:
   7. removed += 1
   8. return removed

2. 2 Count the runs on Example 1

   Example 1 has 5 intervals. Sorting 5 items takes about 5 × log₂ 5, so about 12 steps. The loop then runs 5 times.

   12 + 5 = about 17 steps.

   part	sort	loop
   steps	about 5 × log 5 ≈ 12	5

3. 3 Write the count for any n

   n log₂ n (sort) + n (loop)

   Check it with Example 1: 5 × 2.3 + 5 ≈ 17.

4. 4 Keep only the part that grows fastest

   Keep the sort. log n keeps growing, so n log n pulls away from the loop’s n. What is left is n log n.

   So the time is O(n log n).

5. S Space: count the extra memory the same way

   The loop keeps only removed and last_end. Sorting in place needs little extra memory, though some languages use up to O(n) for it. Beyond the sort, the space is O(1).

   removedlast_endsort space

Common mistake

Sorting by start and keeping the first

Sorted by start, a long interval that starts early, like [1, 10], would be kept first. It then blocks [2, 3], [4, 5] and [6, 7]. Sorting by end keeps the three short ones and removes only [1, 10].

Tested at the limits

2,000 random lists of 1 to 8 intervals with ends from −4 to 4, so touching ends, nesting and repeats come up often. Longest chain and greedy by end gave the same answer every time.

Largest inputs	Result
100,000 intervals (the most allowed), shuffled, each one there twice, so half must go. Greedy by end. Also run with 100,000 that only touch, where none go.	0.04 s, and about 1.5 MB of extra memory, all for the sort. The greedy loop itself keeps only a few numbers.
2,000 intervals. Longest chain, about 2 million pairs.	0.17 s. At 100,000 intervals it would check 5 billion pairs.