力扣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

---