Non-overlapping Intervals

NeetCode: Non-overlapping Intervals · LeetCode: 435. Non-overlapping Intervals · Difficulty: Medium

Given an array of intervals [start, end], return the minimum number of intervals to remove so that the remaining ones do not overlap. Intervals that only touch at an endpoint ([1,2] and [2,3]) do not overlap.

Example

Text

Input:  intervals = [[1,2],[2,4],[1,4]]    Output: 1    (remove [1,4])
Input:  intervals = [[1,2],[2,4]]          Output: 0

Brute force: longest chain by DP

Removing the fewest intervals is the same as keeping the most. Sort by start; let dp[i] be the largest set of non-overlapping intervals that ends with interval i. Then dp[i] = 1 + max(dp[j]) over earlier j with end_j <= start_i. The answer is n - max(dp).

Java

import java.util.Arrays;

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        int n = intervals.length;
        if (n == 0) {
            return 0;
        }
        int[][] sorted = intervals.clone();
        Arrays.sort(sorted, (a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int longest = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (sorted[j][1] <= sorted[i][0]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            longest = Math.max(longest, dp[i]);
        }
        return n - longest;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.eraseOverlapIntervals(new int[][] {{1, 2}, {2, 4}, {1, 4}}));
        System.out.println(solution.eraseOverlapIntervals(new int[][] {{1, 2}, {2, 4}}));
        System.out.println(solution.eraseOverlapIntervals(new int[][] {{1, 2}, {1, 2}, {1, 2}}));
    }
}

Output

1
0
2

Time: O(n^2). Space: O(n).

Optimal: sort by end, keep whatever ends earliest

This is the activity-selection greedy. Sort by end. Always keep the interval that finishes first, because finishing early leaves the most room for the rest; any conflicting interval that starts before that end is removed. Keep the end of the last kept interval; an interval whose start is >= end is kept and updates the end; otherwise it overlaps and counts as one removal.

Sorting by end (not start) is what makes the choice safe: among overlapping intervals, the one with the smallest end can never block more future intervals than the others.

Java

import java.util.Arrays;

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }
        int[][] sorted = intervals.clone();
        Arrays.sort(sorted, (a, b) -> Integer.compare(a[1], b[1]));
        int keptEnd = sorted[0][1];
        int removed = 0;
        for (int i = 1; i < sorted.length; i++) {
            if (sorted[i][0] >= keptEnd) {
                keptEnd = sorted[i][1];
            } else {
                removed++;
            }
        }
        return removed;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.eraseOverlapIntervals(new int[][] {{1, 2}, {2, 4}, {1, 4}}));
        System.out.println(solution.eraseOverlapIntervals(new int[][] {{1, 2}, {2, 4}}));
        System.out.println(solution.eraseOverlapIntervals(new int[][] {{1, 2}, {1, 2}, {1, 2}}));
    }
}

Output

1
0
2

Time: O(n log n). Space: O(n) for the sorted copy of the outer array.