#435

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Non-overlapping Intervals

Determine the minimum number of intervals to remove from a list to ensure no intervals overlap using dynamic programming and greedy insights.

array dynamic programming greedy sorting

Problem Statement

Given an array of intervals where each interval is represented as [start, end], compute the minimum number of intervals to remove so that no two remaining intervals overlap. Intervals that only touch at their boundaries are considered non-overlapping.

For example, given intervals = [[1,2],[2,3],[3,4],[1,3]], removing [1,3] ensures the rest are non-overlapping. Your task is to implement a function that returns this minimum removal count efficiently, considering large input constraints.

Examples

Example 1

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]

Output: 1

[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

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

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

Solution Approach

Sort Intervals by End Time

Begin by sorting intervals based on their end times. This ordering allows a greedy approach to pick the maximum number of non-overlapping intervals, which simplifies the calculation of how many intervals must be removed.

Dynamic Programming State Transition

Define dp[i] as the maximum number of non-overlapping intervals ending at the i-th interval. For each interval, check all previous intervals that end before its start and update dp[i] as dp[i] = max(dp[j] + 1) to maintain the optimal state transition.

Calculate Minimum Removals

Once the maximum count of non-overlapping intervals is known from the DP array or greedy selection, subtract this count from the total number of intervals. This difference is the minimum number of intervals to remove.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Sorting takes O(n log n) time, the DP approach can take O(n^2) in the worst case, but a greedy approach reduces it to O(n log n). Space complexity is O(n) for the DP array, and O(1) extra for the greedy method.

What Interviewers Usually Probe

Do you consider intervals that only touch at endpoints as overlapping?
Can you optimize the DP solution using a greedy approach for larger inputs?
What is the trade-off between tracking maximum intervals kept vs. counting removals directly?

Common Pitfalls or Variants

Common pitfalls

Assuming intervals touching at endpoints overlap, which leads to extra removals.
Not sorting intervals properly before applying DP or greedy approach, causing incorrect state updates.
Attempting a brute-force check of all subsets, which exceeds time limits for large inputs.

Follow-up variants

Find the maximum number of non-overlapping intervals instead of minimum removals.
Allow intervals with equal start and end times and count how many need removal.
Apply the same logic to weighted intervals where each interval has a value and the goal is maximum total value non-overlapping.

FAQ

Do intervals that only touch count as overlapping in Non-overlapping Intervals?

No, intervals touching only at endpoints are considered non-overlapping and should not be removed.

Is sorting intervals necessary for the optimal solution?

Yes, sorting by end times enables the greedy approach and simplifies DP state transitions for efficiency.

What is the difference between DP and greedy approaches for this problem?

DP tracks the maximum intervals that can be kept considering all prior compatible intervals, while greedy chooses the earliest ending interval to minimize removals efficiently.

How do I handle very large input sizes up to 10^5?

Use the greedy end-time approach to achieve O(n log n) time, avoiding the O(n^2) DP computation for large arrays.

Can this problem pattern be applied to other interval scheduling problems?

Yes, the state transition dynamic programming pattern and greedy end-time strategy generalize to various interval selection and removal problems.

terminal

Solution

Solution 1: Sorting + Greedy

We first sort the intervals in ascending order by their right boundary. We use a variable $\textit{pre}$ to record the right boundary of the previous interval and a variable $\textit{ans}$ to record the number of intervals that need to be removed. Initially, $\textit{ans} = \textit{intervals.length}$.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])
        ans = len(intervals)
        pre = -inf
        for l, r in intervals:
            if pre <= l:
                ans -= 1
                pre = r
        return ans

Continue Practicing

#646 maximum length of pair chain #1262 greatest sum divisible by three #1363 largest multiple of three