Scale Engineer

Non-overlapping Intervals

Med
#0422Time: 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: O(N), where N is the number of intervals. This is for the `dp` array used to store intermediate results.7 companies
Patterns
Dynamic ProgrammingGreedy
Algorithms
Sorting
Data structures
Array
Companies
J.P. MorganSnowflakeYandexZoho

Prompt

Given an array of intervals intervals where intervals[i] = [starti, endi], 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 <= 105
  • intervals[i].length == 2
  • -5 * 104 <= starti < endi <= 5 * 104

Approaches

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

O(N), where N is the number of intervals. This is for the `dp` array used to store intermediate results.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem