算法训练营Day36（贪心5）
说明
今天的三道题目，都算是 重叠区间 问题，可以好好感受一下。 都属于那种看起来好复杂，但一看贪心解法，惊呼：这么巧妙！
还是属于那种，做过了也就会了，没做过就很难想出来。
不过把如下三题做了之后， 重叠区间 基本上差不多了
435. 无重叠区间 力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
if not intervals:
return 0
intervals.sort(key=lambda x: x[0]) # 按照左边界升序排序
count = 0 # 记录重叠区间数量
for i in range(1, len(intervals)):
if intervals[i][0] < intervals[i - 1][1]: # 存在重叠区间
intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]) # 更新重叠区间的右边界
count += 1
return count763.划分字母区间 力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
class Solution:
def partitionLabels(self, s: str) -> List[int]:
last_occurrence = {} # 哈希表存储每个字符最后出现的位置
for i, ch in enumerate(s):
last_occurrence[ch] = i
result = []
start = 0
end = 0
for i, ch in enumerate(s):
end = max(end, last_occurrence[ch]) # 找到当前字符出现的最远位置
if i == end: # 如果当前位置是最远位置，表示可以分割出一个区间
result.append(end - start + 1)
start = i + 1
return result
56. 合并区间 力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
本题相对来说就比较难了。
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
result = []
if len(intervals) == 0:
return result # 区间集合为空直接返回
intervals.sort(key=lambda x: x[0]) # 按照区间的左边界进行排序
result.append(intervals[0]) # 第一个区间可以直接放入结果集中
for i in range(1, len(intervals)):
if result[-1][1] >= intervals[i][0]: # 发现重叠区间
# 合并区间，只需要更新结果集最后一个区间的右边界，因为根据排序，左边界已经是最小的
result[-1][1] = max(result[-1][1], intervals[i][1])
else:
result.append(intervals[i]) # 区间不重叠
return result原文地址：https://blog.csdn.net/2301_79788081/article/details/135687112
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！