題目簡介
435. 無重疊區(qū)間
給定一個區(qū)間的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除區(qū)間的最小數(shù)量柒竞，使剩余區(qū)間互不重疊 低缩。
763. 劃分字母區(qū)間
給你一個字符串 s 。我們要把這個字符串劃分為盡可能多的片段蟀俊，同一字母最多出現(xiàn)在一個片段中。
注意，劃分結(jié)果需要滿足：將所有劃分結(jié)果按順序連接诫尽，得到的字符串仍然是 s 。
返回一個表示每個字符串片段的長度的列表炬守。
56. 合并區(qū)間
以數(shù)組 intervals 表示若干個區(qū)間的集合牧嫉，其中單個區(qū)間為 intervals[i] = [starti, endi] 。請你合并所有重疊的區(qū)間减途，并返回 一個不重疊的區(qū)間數(shù)組酣藻，該數(shù)組需恰好覆蓋輸入中的所有區(qū)間 。
初見思路
- 一次遍歷鳍置，存在重疊區(qū)間辽剧，計數(shù)加一，同時更新當前區(qū)間最小右邊界税产。
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 count
763.使用字典記錄每個字母的最大位置怕轿，使得字母盡可能出現(xiàn)在同一個窗口中。完成一個窗（i==r）就把它的長度記錄下來辟拷。
class Solution:
def partitionLabels(self, s: str) -> List[int]:
if len(s) == 1:
return [0]
word_dict = [0] * 26
for i,ch in enumerate(s):
word_dict[ord(ch) - ord('a')] = i # 更新每個字母的最大位置
l,r,ans = 0,0,list()
for i,ch in enumerate(s):
r = max(r, word_dict[ord(ch) - ord('a')])
if i == r:
ans.append(r-l+1)
l = r + 1
return ans
56.區(qū)間經(jīng)典題目撞羽，記住這個題的用法，很多題目都用得到衫冻。
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
if len(intervals) == 0:
return list()
intervals.sort(key=lambda x:x[0])
ans = [intervals[0]]
for i in range(1,len(intervals)):
if ans[-1][1] >= intervals[i][0]:
ans[-1][1] = max(ans[-1][1], intervals[i][1])
else:
ans.append(intervals[i])
return ans
復盤思路
https://programmercarl.com/0435.%E6%97%A0%E9%87%8D%E5%8F%A0%E5%8C%BA%E9%97%B4.html
https://programmercarl.com/0763.%E5%88%92%E5%88%86%E5%AD%97%E6%AF%8D%E5%8C%BA%E9%97%B4.html
https://programmercarl.com/0056.%E5%90%88%E5%B9%B6%E5%8C%BA%E9%97%B4.html
