Non-overlapping Intervals

Medium Intervals Basics Original on LeetCode

Reported atGoogle

Non-overlapping Intervals is a medium intervals problem solved with the basics pattern. The best approach, optimal (greedy by earliest end), runs in O(n log n) time and O(log n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (sort by start + longest chain dp) up.

Problem

You are given an array of intervals where intervals[i] = [start, end]. Return the minimum number of intervals you must remove so that the remaining intervals do not overlap each other.

Two intervals that only touch at an endpoint, such as [1, 2] and [2, 3], are not considered overlapping.

Examples

Example 1

Input
intervals = [[2, 5], [1, 3], [4, 7], [6, 8]]
Output
2
Why
Keeping [1, 3] and [4, 7] (or [1, 3] and [6, 8]) leaves no overlaps; at most two intervals can stay, so two must go.

Example 2

Input
intervals = [[1, 2], [2, 3], [3, 4]]
Output
0
Why
Intervals that only touch at an endpoint do not overlap.

Example 3

Input
intervals = [[0, 10], [1, 2], [3, 4], [5, 6]]
Output
1
Why
Removing the long interval [0, 10] is enough; the three short ones are disjoint.

Constraints

  • 1 <= intervals.length <= 10^5
  • intervals[i].length == 2
  • -5 * 10^4 <= start < end <= 5 * 10^4

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (sort by start + longest chain DP)O(n²)O(n)
Optimal (greedy by earliest end)O(n log n)O(log n)

1Brute force (sort by start + longest chain DP)

TimeO(n²)Each interval looks back at every earlier interval.
SpaceO(n)The dp array.

Sort by start. Let dp[i] be the largest number of non-overlapping intervals that can be kept with interval i as the last one. It is 1 plus the best dp[j] over earlier intervals j that end at or before start[i]. The answer is n minus the largest dp value.

  1. Sort intervals by start.
  2. dp[i] = 1 + max(dp[j]) over j < i with end[j] <= start[i] (or 1 if none).
  3. Return n - max(dp).
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        int n = intervals.length;
        int[][] a = intervals.clone();
        Arrays.sort(a, (x, y) -> Integer.compare(x[0], y[0]));
        int[] dp = new int[n];
        int best = 0;
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (a[j][1] <= a[i][0]) dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            best = Math.max(best, dp[i]);
        }
        return n - best;
    }
}

2Optimal (greedy by earliest end)

TimeO(n log n)Sorting dominates; the sweep is linear.
SpaceO(log n)Only the sort's own stack (the sweep uses two variables).

Among all intervals that could come next, keeping the one that ends first never hurts: it leaves the most room for the rest. So sort by end, sweep once, keep an interval if it starts at or after the end of the last kept one, and count every other interval as removed.

  1. Sort intervals by end.
  2. lastEnd = end of the first interval, kept = 1.
  3. For each next interval: if start >= lastEnd, keep it (kept++, lastEnd = its end); otherwise it is removed.
  4. Return n - kept.
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (x, y) -> Integer.compare(x[1], y[1]));
        int kept = 1;
        int lastEnd = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= lastEnd) {
                kept++;
                lastEnd = intervals[i][1];
            }
        }
        return intervals.length - kept;
    }
}

Edge cases to test

  • A single interval (answer 0)
  • Intervals that only share an endpoint (not an overlap)
  • Duplicate intervals
  • One long interval covering many short ones: remove the long one, not the short ones
  • Negative coordinates

Hints

Hint 1

Removing as few intervals as possible is the same as keeping as many pairwise non-overlapping intervals as possible.

Hint 2

Which interval is the safest to keep first? The one that frees up the timeline the earliest.

Hint 3

Sort by end point. Keep an interval whenever its start is at or after the end of the last kept interval; count the rest as removed.

FAQ

What is the best time complexity for Non-overlapping Intervals?

Optimal (greedy by earliest end) runs in O(n log n) time and O(log n) extra space. Sorting dominates; the sweep is linear.

Which pattern does Non-overlapping Intervals use?

It is a intervals problem that uses the basics pattern. Other problems with the same pattern: Detect overlap unsorted, Detect overlap sorted intervals, Interval List Intersections.

Is there a brute force solution for Non-overlapping Intervals?

Yes. Brute force (sort by start + longest chain DP) takes O(n²) time and O(n) space. Sort by start.

Which edge cases should I test for Non-overlapping Intervals?

A single interval (answer 0); Intervals that only share an endpoint (not an overlap); Duplicate intervals; One long interval covering many short ones: remove the long one, not the short ones; Negative coordinates.