代码随想录 -- 贪心 -- 合并区间
56. 合并区间 - 力扣(LeetCode)
思路:
先按照左边界从大到小对数组进行排序;
遍历数组:如果当前遍历的区间左边界小于等于前一个区间的右边界,更新当前区间的左边界为最小的左边界,右边界为最大的右边界;如果没有重叠,就将前一个区间加入res中。
问题:最后一个区间没法加入res中,所以我在数组最后添加了一个元素[100000,100000]。
class Solution(object):
def merge(self, intervals):
intervals.sort(key=lambda x:(x[0],x[1]))
intervals.append([100000,100000])
res=[]
for i in range(1,len(intervals)):
if intervals[i][0]<=intervals[i-1][1]:
intervals[i][0]=min(intervals[i-1][0],intervals[i][0])
intervals[i][1]=max(intervals[i-1][1],intervals[i][1])
else:
res.append(intervals[i-1])
return res
题解思路:
将排序后的第一个元素直接加入res中;
遍历数组:如果当前元素的左边界小于等于res中的最后一个元素的右边界,说明重叠,则更新res的最后一个元素的右边界为最大的右边界;否则直接将当前元素加入res中。
class Solution(object):
def merge(self, intervals):
intervals.sort(key=lambda x:(x[0],x[1]))
res=[intervals[0]]
for i in range(1,len(intervals)):
if intervals[i][0]<=res[-1][1]:
res[-1][1]=max(intervals[i][1],res[-1][1])
else:
res.append(intervals[i])
return res