题目简介
435. 无重叠区间
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
763. 划分字母区间
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
56. 合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
初见思路
- 一次遍历，存在重叠区间，计数加一，同时更新当前区间最小右边界。
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.使用字典记录每个字母的最大位置，使得字母尽可能出现在同一个窗口中。完成一个窗（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.区间经典题目，记住这个题的用法，很多题目都用得到。
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
