Non-overlapping Intervals

MEDIUM

Description

Given an array of intervals intervals where intervals[i] = [start_i, end_i], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note that intervals which only touch at a point are non-overlapping. For example, [1, 2] and [2, 3] are non-overlapping.

Example 1:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

Example 2:

Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.

Example 3:

Input: intervals = [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

Constraints:

1 <= intervals.length <= 10⁵
intervals[i].length == 2
-5 * 10⁴ <= start_i < end_i <= 5 * 10⁴

Approaches

Checkout 3 different approaches to solve Non-overlapping Intervals. Click on different approaches to view the approach and algorithm in detail.

Dynamic Programming

This approach uses dynamic programming, which is a common technique for optimization problems. The idea is to build up a solution by finding the optimal solution for smaller subproblems. We sort the intervals by their start times and then, for each interval, we determine the maximum number of non-overlapping intervals that can be formed ending with that interval. This is analogous to solving the Longest Increasing Subsequence problem.

Algorithm

Sort the intervals array based on the start times of the intervals.
Create a dynamic programming array dp of size n, where n is the number of intervals.
dp[i] will store the maximum number of non-overlapping intervals in a sequence that ends with intervals[i].
Initialize all elements of dp to 1, as any single interval is a valid non-overlapping set.
Iterate from the second interval (i = 1) to the end. For each intervals[i], iterate through all preceding intervals j (from 0 to i-1).
If intervals[j] does not overlap with intervals[i] (i.e., intervals[j][1] <= intervals[i][0]), it means intervals[i] can extend the non-overlapping sequence ending at intervals[j]. Update dp[i] accordingly: dp[i] = max(dp[i], 1 + dp[j]).
After the loops complete, find the maximum value in the dp array. This value, maxKept, is the size of the largest set of non-overlapping intervals.
The minimum number of intervals to remove is n - maxKept.

First, we sort the intervals based on their start times. This ordering is crucial as it allows us to build our solution sequentially. We define dp[i] as the maximum number of compatible (non-overlapping) intervals we can select from the first i intervals, with the condition that the i-th interval must be included in our selection.

We initialize dp[i] = 1 for all i, because a single interval by itself is always a valid non-overlapping set. Then, we iterate through the intervals from i = 1 to n-1. For each i, we look back at all previous intervals j < i. If intervals[j] and intervals[i] are non-overlapping (i.e., intervals[j][1] <= intervals[i][0]), we can potentially form a longer sequence of non-overlapping intervals by appending intervals[i] to the sequence ending at intervals[j]. We update dp[i] to be the maximum of its current value and 1 + dp[j].

After computing all dp values, the maximum value in the dp array gives the size of the largest possible non-overlapping set of intervals. The minimum number of intervals to remove is then the total number of intervals minus this maximum size.

import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }

        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));

        int n = intervals.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);

        int maxKept = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (intervals[j][1] <= intervals[i][0]) {
                    dp[i] = Math.max(dp[i], 1 + dp[j]);
                }
            }
            maxKept = Math.max(maxKept, dp[i]);
        }

        return n - maxKept;
    }
}

Complexity Analysis

Time Complexity: O(N^2), where N is the number of intervals. The dominant part is the nested loop used to fill the `dp` array. The initial sort takes O(N log N).Space Complexity: O(N), where N is the number of intervals. This is for the `dp` array used to store intermediate results.

Pros and Cons

Pros:

It is a systematic approach that guarantees finding the optimal solution.
The logic is a standard application of dynamic programming.

Cons:

The O(N^2) time complexity makes it too slow for the given constraints, leading to a 'Time Limit Exceeded' error on large inputs.

Code Solutions

Checking out 3 solutions in different languages for Non-overlapping Intervals. Click on different languages to view the code.

class Solution {
public
  int eraseOverlapIntervals(int[][] intervals) {
    Arrays.sort(intervals, Comparator.comparingInt(a->a[1]));
    int t = intervals[0][1], ans = 0;
    for (int i = 1; i < intervals.length; ++i) {
      if (intervals[i][0] >= t) {
        t = intervals[i][1];
      } else {
        ++ans;
      }
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Non-overlapping Intervals

Algorithms:

Sorting

Patterns:

Dynamic ProgrammingGreedy

Data Structures:

Array

Companies:

J.P. Morgan |Snowflake |Yandex |Zoho |