435. 无重叠区间
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
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.划分字母区间
class Solution:
def partitionLabels(self, s: str) -> List[int]:
end_dict = {}
# 获取每个字母的最远坐标
for i, ch in enumerate(s):
end_dict[ch] = i
start = 0
end = 0
res = []
for i, ch in enumerate(s):
# 更新每个字母的最远坐标
end = max(end, end_dict[ch])
# 遍历到这个区间的最远坐标，划分区间
if i == end:
res.append(end - start + 1)
start = i + 1
return res
56. 合并区间
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key=lambda x: x[0])
res = []
res.append(intervals[0])
for i in range(1, len(intervals)):
if res[-1][1] >= intervals[i][0]:
res[-1][1] = max(intervals[i][1], res[-1][1])
else:
res.append(intervals[i])
return res