LeetCode无重叠区间问题自定义贪心解法输出错误原因咨询

核心错误 #

你的贪心策略逻辑存在错误：该问题的最优贪心选择是重叠时优先保留结束位置更早的区间，而非你采用的「保留长度更短的区间」。只有保留结束更早的区间，才能给后续未遍历的区间留出最大的可用空间，最终实现最少的区间移除次数。

举个简单的反例即可验证：
测试用例 [[1,3], [2,4], [3,5]]

• 按照你的策略：前两个区间长度相等，你会移除前一个区间[1,3]，保留[2,4]；后续遍历到[3,5]时和[2,4]重叠，需要再移除一个区间，总移除次数为2。
• 最优解：移除中间的[2,4]，保留前后两个不重叠的区间，总移除次数仅为1。

你的策略在上述场景中做出了错误选择，你提供的测试用例同样存在这类场景，所以最终结果比正确答案多了1。

代码修复方案 #

只需要修改重叠时的判断逻辑，把比较区间长度改为比较区间的结束位置即可，修改后的完整代码如下：

from typing import List
class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        L = len(intervals)
        if L <= 1:
            return 0
        
        intervals.sort(key = lambda x: (x[0], x[1]))
        prev_idx = 0
        curr_idx = 1
        interval_cnt = 0
        while curr_idx < L:
            # 区间重叠
            if intervals[curr_idx][0] < intervals[prev_idx][1]:
                interval_cnt += 1
                # 保留结束更早的区间，移除结束更晚的
                if intervals[curr_idx][1] < intervals[prev_idx][1]:
                    prev_idx = curr_idx
            else: # 区间不重叠
                prev_idx = curr_idx
            curr_idx += 1
               
        return interval_cnt

用修改后的代码重新运行你的测试用例，就能得到正确结果7。

内容的提问来源于stack exchange，提问作者flashburn