【代码随想录训练营】【Day 38】【贪心-5】| Leetcode 435, 763, 56
【代码随想录训练营】【Day 38】【贪心-5】| Leetcode 435, 763, 56
需强化知识点
- 重叠区间系列 题， 763， 435
题目
435. 无重叠区间
- 左起点排序，记录重叠区间个数，总数相减即为结果，过程中维护右边界
- 注意：出现重叠区域时，右边界取最小值，即保留更靠左的区间，来使得后面区间更有可能不重合，从而移除次数最少
class Solution:def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:intervals.sort(key = lambda x: x[0])times = 0sr = intervals[0][1]for i in range(1, len(intervals)):if intervals[i][0] >= sr:sr = intervals[i][1]else:times += 1sr = min(sr, intervals[i][1])return times763. 划分字母区间
- 思路：记录每个字母出现的最大位置，然后再次遍历，当遇到 i == 最大位置时，则可以切分一次
class Solution:def partitionLabels(self, s: str) -> List[int]:label_index = [-1] * 26result = []max_right = -1start_index = 0for i, c in enumerate(s):label_index[ord(c) - ord('a')] = max(label_index[ord(c) - ord('a')], i)for i , c in enumerate(s):max_right = max(max_right, label_index[ord(c) - ord('a')])if i == max_right:result.append(i - start_index + 1)start_index = i+1return result
56. 合并区间
- 思路：遇到重叠进行合并，遇到不重叠，保存之前区间
class Solution:def merge(self, intervals: List[List[int]]) -> List[List[int]]:intervals.sort(key = lambda x: x[0])result = []sl, sr = intervals[0][0], intervals[0][1]for i in range(1, len(intervals)):if intervals[i][0] <= sr:sr = max(sr, intervals[i][1])else:result.append([sl, sr])sl, sr = intervals[i][0], intervals[i][1]result.append([sl, sr])return result