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.

#435

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

无重叠区间

给定一个区间的集合 intervals ，其中 intervals[i] = [start i , end i ] 。返回需要移除区间的最小数量，使剩余区间互不重叠。注意只在一点上接触的区间是不重叠的。例如 [1, 2] 和 [2, 3] 是不重叠的。示例 1: 输入: interva…

数组动态规划贪心排序

题目描述

给定一个区间的集合 intervals ，其中 intervals[i] = [start_i, end_i] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

注意只在一点上接触的区间是 不重叠的。例如 [1, 2] 和 [2, 3] 是不重叠的。

示例 1:

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2:

输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:

输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

提示:

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

lightbulb

解题思路

方法一：排序 + 贪心

我们首先将区间按照右边界升序排序，用一个变量 $\textit{pre}$ 记录上一个区间的右边界，用一个变量 $\textit{ans}$ 记录需要移除的区间数量，初始时 $\textit{ans} = \textit{intervals.length}$ 。

然后遍历区间，对于每一个区间：

若当前区间的左边界大于等于 $\textit{pre}$ ，说明该区间无需移除，直接更新 $\textit{pre}$ 为当前区间的右边界，然后将 $\textit{ans}$ 减一；
否则，说明该区间需要移除，不需要更新 $\textit{pre}$ 和 $\textit{ans}$ 。

最后返回 $\textit{ans}$ 即可。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 为区间的数量。

1

2

3

4

5

6

7

8

9

10

11

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#646 最长数对链 #1262 可被三整除的最大和 #1363 形成三的最大倍数