☕ DSA Java Articles

Topics › Greedy Algorithms › Medium/Hard

Non-overlapping Intervals

Medium TUF ID 550 A2ZBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an array of intervals intervals[i] = [start_i, end_i] with start_i < end_i. Return the minimum number of intervals to remove so that the remaining intervals do not overlap. Intervals that only touch at an endpoint, such as [1, 2] and [2, 3], do not overlap here (think of them as half-open, [start, end)).

Constraints: 1 ≤ n ≤ 10^5, -5 × 10^4 ≤ start_i < end_i ≤ 5 × 10^4.

Example 1

intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
answer = 1

Removing [1, 3] leaves [1, 2], [2, 3], [3, 4], which only touch.

Example 2

intervals = [[1, 2], [1, 2], [1, 2]]
answer = 2

The three copies all overlap each other, so only one can stay.

Reframing. Removing as few intervals as possible is the same as keeping as many as possible: answer = n - (largest set of pairwise non-overlapping intervals). That second problem is the classic activity selection problem, and all three approaches below compute it.

Approach 1: Brute force, every subset

Intuition. Enumerate every subset of intervals, check whether it is pairwise non-overlapping, and remember the largest valid one. To check a subset quickly, sort it by start: the subset is valid exactly when each interval ends no later than the next one starts. Checking only neighbours is enough, because if a ends before b starts and b ends before c starts, then a certainly ends before c starts.

Algorithm.

  1. For every bitmask, collect the chosen intervals and sort them by start.
  2. If every neighbouring pair satisfies chosen[k].end ≤ chosen[k+1].start, the subset is valid; update bestKept.
  3. Return n - bestKept.
static int bruteForce(int[][] intervals) {
    int n = intervals.length;
    int bestKept = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        List<int[]> chosen = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (((mask >> i) & 1) == 1) chosen.add(intervals[i]);
        }
        chosen.sort((x, y) -> Integer.compare(x[0], y[0]));
        boolean ok = true;
        for (int k = 0; k + 1 < chosen.size(); k++) {
            if (chosen.get(k)[1] > chosen.get(k + 1)[0]) {    // the next one starts before this one ends
                ok = false;
                break;
            }
        }
        if (ok) bestKept = Math.max(bestKept, chosen.size());
    }
    return n - bestKept;
}

Complexity. Time O(2^n · n log n). Space O(n). Only usable as a checker for tiny inputs.

Approach 2: Better, DP like longest increasing subsequence

Intuition. Sort by start. A valid kept set, read in that order, is a chain where each interval starts at or after the previous one ends. Finding the longest such chain is the same shape as Longest Increasing Subsequence: let dp[i] be the most intervals we can keep if a[i] is the last kept one. Then dp[i] = 1 + max(dp[j]) over earlier j with a[j].end ≤ a[i].start, or 1 if there is none. The answer is n - max(dp).

Because every interval has start < end, the predecessor of a[i] in a chain always starts strictly earlier, so it really does appear at a smaller index after sorting by start.

Algorithm.

  1. Sort a copy by start.
  2. For each i, set dp[i] = 1 and try every j < i with a[j].end ≤ a[i].start.
  3. Return n - max(dp).
static int better(int[][] intervals) {
    int n = intervals.length;
    if (n == 0) return 0;
    int[][] a = intervals.clone();
    Arrays.sort(a, (x, y) -> Integer.compare(x[0], y[0]));
    int[] dp = new int[n];                                    // dp[i] = most intervals we can keep ending with a[i]
    int bestKept = 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);
        }
        bestKept = Math.max(bestKept, dp[i]);
    }
    return n - bestKept;
}

Complexity. Time O(n^2) for the double loop (sorting is O(n log n)). Space O(n) for dp. With n = 10^5 that is 10^10 steps, still too slow.

Approach 3: Optimal, greedy by earliest end

Intuition. Which interval should be the first one we keep? The one that ends earliest. It leaves the most room for everything after it.

Exchange argument: take any optimal kept set and look at its first interval f (smallest end). Let e be the interval with the smallest end overall, so e.end ≤ f.end. Every other kept interval starts at or after f.end, hence at or after e.end. So replacing f by e keeps the set valid and the same size. There is always an optimal solution that starts with e. After committing to e, the intervals that start before e.end cannot be kept, and the rest is the same problem again, so we repeat: walk the intervals in order of end and keep each one that starts at or after the last kept end.

Sorting by start instead fails. In [[1, 100], [2, 3], [4, 5]], the earliest start is [1, 100], which blocks both of the others; ending earliest picks [2, 3] and [4, 5].

Algorithm.

  1. Sort a copy by end.
  2. Keep the first interval: kept = 1, lastEnd = a[0].end.
  3. For each next interval: if start ≥ lastEnd, keep it and set lastEnd = end; otherwise it would be removed.
  4. Return n - kept.
static int optimal(int[][] intervals) {
    int n = intervals.length;
    if (n == 0) return 0;
    int[][] a = intervals.clone();
    Arrays.sort(a, (x, y) -> Integer.compare(x[1], y[1]));   // compare, never subtract: x[1] - y[1] can overflow
    int kept = 1, lastEnd = a[0][1];
    for (int i = 1; i < n; i++) {
        if (a[i][0] >= lastEnd) {                             // touching is allowed
            kept++;
            lastEnd = a[i][1];
        }
    }
    return n - kept;
}

Dry run on [[1, 100], [11, 22], [1, 11], [2, 12]], sorted by end to [[1, 11], [2, 12], [11, 22], [1, 100]]:

interval lastEnd before start ≥ lastEnd? kept lastEnd after
[1, 11] - first 1 11
[2, 12] 11 2 < 11, remove 1 11
[11, 22] 11 11 ≥ 11, keep 2 22
[1, 100] 22 1 < 22, remove 2 22

Four intervals, two kept, so remove 2.

Complexity. Time O(n log n) for the sort; the scan is O(n). Space O(n) for the sorted copy of references (or O(1) extra if sorting the input in place is allowed).

Edge cases and pitfalls