LeetCode 435. Non-overlapping Intervals 题解题目描述给定一个区间的集合intervals其中intervals[i] [starti, endi]。返回需要移除的区间的最小数量使得剩下的区间互不重叠。示例 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 解释: 你不需要移除任何区间因为它们已经是无重叠的了。解题思路方法贪心算法思路贪心算法的核心思想是在每一步选择中都采取在当前状态下最好或最优的选择从而希望导致结果是全局最好或最优的。对于这个问题我们可以按照区间的结束时间进行排序。遍历排序后的区间维护一个变量end表示当前不重叠区间的结束时间。如果当前区间的开始时间大于等于end说明这个区间与之前的区间不重叠更新end为当前区间的结束时间。否则说明这个区间与之前的区间重叠需要移除增加计数器。复杂度分析时间复杂度O(n log n)其中 n 是区间的数量。排序的时间复杂度是 O(n log n)遍历的时间复杂度是 O(n)。空间复杂度O(1)只需要常数级的额外空间。代码实现方法贪心算法class Solution: def eraseOverlapIntervals(self, intervals: List[List[int]]) - int: # 按照区间的结束时间进行排序 intervals.sort(keylambda x: x[1]) # 初始化变量 end float(-inf) count 0 # 遍历排序后的区间 for interval in intervals: # 如果当前区间的开始时间大于等于 end说明不重叠 if interval[0] end: # 更新 end 为当前区间的结束时间 end interval[1] else: # 区间重叠需要移除 count 1 # 返回需要移除的区间数量 return count测试用例测试用例 1输入intervals [[1,2],[2,3],[3,4],[1,3]]输出1测试用例 2输入intervals [[1,2],[1,2],[1,2]]输出2测试用例 3输入intervals [[1,2],[2,3]]输出0总结本题是贪心算法的经典问题主要考察对贪心算法思想的理解和应用。通过排序和遍历的方法我们可以高效地找到需要移除的最小区间数量。贪心算法的核心思想是在每一步选择中都采取在当前状态下最好或最优的选择从而希望导致结果是全局最好或最优的。这种方法不仅适用于无重叠区间问题还可以应用于许多其他需要区间调度的问题。掌握贪心算法的原理对于理解算法设计思想非常重要。