435. 无重叠区间
给定一个区间的集合 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],x[1]))
result = 0
for i in range(1, len(intervals)):
if intervals[i-1][1]>intervals[i][0]:
#区间重叠
result += 1
intervals[i][1] = min(intervals[i-1][1], intervals[i][1])
return result
763.划分字母区间
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
解题思路：
要想得到最大区间，需要先遍历整个s，记录每个字母的最大index，例如用hash_table记录。设置start，end记录每个字符片段的起始，并在第二次遍历的时候更新end，当i==end时说明遍历到了当前字符片段的终点，添加进result并更新start。
class Solution:
def partitionLabels(self, s: str) -> List[int]:
hash_table = {}
for i , j in enumerate(s):
hash_table[j] = i#get the farest index for each letter
result = []
start = 0
end = 0
for i,j in enumerate(s):
end = max(end, hash_table[j])#update the end idx to the farest
if i == end:#meet the last idx of this interval
result.append(end-start+1)
start = i+1
return result56. 合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
解题思路：
本题重点在于发现重叠区间时，直接在result中进行删改而不是在interval中更新，避免后续在result中更改长度。先在result中添加进第一个区间，剩下逻辑与leetcode435类似，如果发现左区间小于上一个右区间，在result中更改最后一个的右区间；否则，在result中添加当前区间。
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key = lambda x:x[0])
result = []
if len(intervals)==1:
result.append(intervals[0])
return result
result.append(intervals[0])
for i in range(1, len(intervals)):
if intervals[i][0]<=result[-1][1]:#有重叠，直接在result中更新
# intervals[i][0] = min(intervals[i-1][0], intervals[i][0])
result[-1][1] = max(result[-1][1], intervals[i][1])
else:
#添加当前区间
result.append(intervals[i])
return result
