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 result
56. 合并区间
以数组 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