代码随想录算法训练营Day30

力扣452.用最少数量的箭引爆气球【medium】
力扣435.无重叠区间【medium】
力扣763.划分字母区间【medium】
力扣56.合并区间【medium】

一、力扣452.用最少数量的箭引爆气球【medium】

题目链接：力扣452.用最少数量的箭引爆气球

视频链接：代码随想录
题解链接：灵茶山艾府

1、思路

• 
• 对区间的右端点进行升序排序
• 初始化 ans = 0, pre = -inf
• 如果 start <= pre：说明这个区间已经有箭，跳过
• 如果 start > pre：说明没有被覆盖住，更新 pre = end，ans += 1
• 时间复杂度：$O(nlogn)$

2、代码

class Solution:def findMinArrowShots(self, points: List[List[int]]) -> int:points.sort(key= lambda x:x[1])ans = 0pre = -inffor start,end in points:if start > pre:ans += 1pre = endreturn ans

---

二、力扣435.无重叠区间【medium】

题目链接：力扣435.无重叠区间

视频链接：代码随想录
题解链接：灵茶山艾府

1、思路

• 求移除最少区间使得剩下的区间之间互不重叠 等价于 选出最多区间使得这些区间互不重叠
• 怎样才可以多呢？我们选出右端点最小的作为第一个区间A，这样相当于为后面预留出更多的位置存放区间，这就是贪心的地方
• 选出第一个后，我们也划去了和A有相交部分的区间，从剩下的区间中再选出最小的右端点
• 所以我们的步骤是
  • 将区间的右端点升序排序
  • 初始化 ans = 0, pre_r = -inf
  • 当碰到区间的左端点 >= 上一个区间的右端点的时候，说明碰到了第一个不相交的了，这就是我们下一个要选的区间， ans += 1 , pre_r = right ,更新区间数ans和右端点的位置
  • 最后的答案用区间长度减一下
• 时间复杂度：$O(nlogn)$

2、代码

class Solution:def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:intervals.sort(key = lambda x: x[1])ans = 0pre_r = -inffor left, right in intervals:if left >= pre_r:ans += 1pre_r = rightreturn len(intervals) - ans

---

三、力扣763.划分字母区间【medium】

题目链接：力扣763.划分字母区间

视频链接：代码随想录
题解链接：灵茶山艾府

1、思路

• 利用字典键的唯一性，确保最终每个字符对应的下标是最后一次出现的位置
• 初始化答案 ans = [ ], start = end = 0
• 记录第一个字母在字符串中最后一次出现的位置更新为end
• 通过for循环遍历，不断延拓更新end【通过比较当前的end和last(c)】，直到 end == i，说明可以切割了，这就是最早可以切割的地方，即贪心的地方
• 那么 i + 1 就是新的start
• 同时记录下刚刚切割的片段长度
• 时间复杂度：$O(2n)$

2、代码

class Solution:def partitionLabels(self, s: str) -> List[int]:last = {c: i for i,c in enumerate(s)} # 每个字母最后出现的下标ans = []start = end = 0for i,c in enumerate(s):end = max(end, last[c]) # 更新当前区间右端点的最大值if end == i: # 当前区间合并完毕ans.append(end - start + 1)start = i + 1  # 下一个区间的左端点return ans

3、代码问题

• {key_expression: value_expression for item in iterable}
• 

---

四、力扣56.合并区间【medium】

题目链接：力扣56.合并区间

题解链接：灵茶山艾府

1、思路

• 对区间左端点进行升序排序
• 初始化答案 ans = [ ]
• 判断什么时候可以合并？
• 当遍历区间的左端点在处理区间的右端点左端，即有相交，即可以合并
  • 合并后还要更新新的右区间
  • 怎么表示这个处理区间的右端点呢？即ans[-1][1]！这个表示太巧妙了！我本来是想引进两个新的变量表示
• 否则，不可以合并，将其作为新的处理区间
  • 即添加到答案中
• 时间复杂度：$O(nlogn)$

2、代码

class Solution:def merge(self, intervals: List[List[int]]) -> List[List[int]]:intervals.sort(key = lambda x:x[0])ans = []for p in intervals:if ans and p[0] <= ans[-1][1]: # 可以合并ans[-1][1] = max(ans[-1][1], p[1]) # 更新右端点最大值else: # 不相交，无法合并ans.append(p) # 新的合并区间return ans

---