我要招人

去企业版

首页 > 试题广场 >

合并区间

[编程题]合并区间

热度指数：178818 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出一组区间，请合并所有重叠的区间。

请保证合并后的区间按区间起点升序排列。

//"区间"定义
class Interval {
   int start; //起点
   int end;   //终点
}

数据范围：区间组数 $0 \le n \le 2 \times 10^5$ ，区间内的值都满足 $0 \le val \le 2 \times 10^5$

要求：空间复杂度 $O(n)$ ，时间复杂度 $O(nlogn)$

进阶：空间复杂度 $O(val)$ ，时间复杂度 $O(val)$

示例1

输入

[[10,30],[20,60],[80,100],[150,180]]

输出

[[10,60],[80,100],[150,180]]

示例2

输入

[[0,10],[10,20]]

输出

[[0,20]]

算法知识视频讲解

Python

牛客314674748号

class Solution:
def merge(self , intervals ):
# write code here
if intervals==[]:
return intervals
intervals.sort(key=lambda x: x.start)
i = 0
out = []
start0 = intervals[0].start
end0 = intervals[0].end
while i < len(intervals)-1:
if end0 >= intervals[i+1].start:
end0 = max(intervals[i+1].end, end0)
else:
out.append(Interval(start0,end0))
start0 = intervals[i+1].start
end0 = intervals[i+1].end
i+=1
out.append(Interval(start0,end0))
return out

发表于 2021-04-16 15:38:06 回复(0)

Python

猫牛

class Solution:
    def merge(self , intervals ):
        # write code here
        if not intervals&nbs***bsp;len(intervals) < 2:
            return intervals
        
        intervals = sorted(intervals, key=lambda a: a.start)
        res = [intervals[0]]
        for inter in intervals[1:]:
            if inter.start <= res[-1].end:
                res[-1].end = max(res[-1].end, inter.end)
            else:
                res.append(inter)
        
        return res

发表于 2021-03-25 02:16:46 回复(0)

Python

牛客795751483号

'<' not supported between instances of 'Interval' and 'Interval'

出现这个错误是什么意思啊

发表于 2021-03-24 08:58:30 回复(0)

Python

LHC0512

Python

class Solution:
    def merge(self, intervals):
        intervals.sort(key=lambda x: x.start)
        i = 1
        while i < len(intervals):
            if intervals[i].start <= intervals[i - 1].end:
                intervals[i] = Interval(intervals[i - 1].start, max(intervals[i - 1].end, intervals[i].end))
                intervals.pop(i - 1)
            else:
                i += 1
        return intervals

发表于 2021-02-23 20:59:52 回复(0)

Python

牛客708526809号

class Solution:
    def merge(self , intervals ):
        # write code here
        result = []
        for i in range(len(intervals)):
            for j in range(len(intervals[i])):
                result.append(intervals[i][j])
        index = 0
        while index < len(result) -1:
            while result[index] > result[index+1]:
                del result[index]
                del result[index]
            index += 1
        final = []
        result.reverse()
        while result:
            temp = []
            for i in range(2):
                temp.append(result.pop())
            final.append(temp)
        return final

我就不明白了，自己输出的都是对的，到这里来全是格式错误

实际输出“Interval”object is not subscriptable 是什么情况，有大神解释一下吗？我的函数里根本没有Interval变量

编辑于 2020-12-11 16:18:58 回复(0)

Python

黄沙遮天

采用的方法是排序后一个个加入进去，是否有重叠的依据就是新元素和最后一个元素的start和end的比较

# class Interval:
#     def __init__(self, a=0, b=0):
#         self.start = a
#         self.end = b

#
# 
# @param intervals Interval类一维数组 
# @return Interval类一维数组
#
class Solution:
    def merge(self , intervals ):
        # write code here
        n=len(intervals)
        if n==0:
            return []
        else:
            intervals.sort(key=lambda x:x.start)
            ans=[]
            ans.append(intervals[0])
            for i in intervals[1:]:
                if i.start<=ans[-1].end:
                    #有重叠
                    if i.end>ans[-1].end:
                        ans[-1].end=i.end
                else:
                    #没有重叠就让其作为最后一个元素
                    #因为是排过序的，所以后面的元素
                    #绝对和前面无重叠
                    ans.append(i)
            return ans

发表于 2020-09-21 16:57:26 回复(0)

Python

风海洋

和大部分人的代码不一样，没有定义两个类，思路却容易理解

class Solution:
    def merge(self , intervals ):
        intervals.sort()#按第一个数字排序以防输入的区间顺序错乱
        list1=[]
        while len(intervals)>1:#为了使后续语句intervals[1][0]不出现越界错误，故设置长度大于1
            if intervals[0][1]<intervals[1][0]:#前一个区间的上界小于后一个区间的下界，说明两个区间没有交集，直接添加
                list1.append(intervals[0])
                intervals.pop(0)#添加完成删除该区间
            else:#否则两个区间有交集
                intervals[0]=[min(intervals[0][0],intervals[1][0]),max(intervals[0][1],intervals[1][1])]#取两个区间的下界的最小值作为合并后区间的下界，取两个区间的上界的最大值作为合并后区间的上界，即完成两个区间的并集
                intervals.pop(1)#合并后intervals的第一个元素用合并后的区间替换，那么参与合并的第二个元素（下标为1）也应该要删除
        list1.append(intervals[0])#intervals还剩一个元素即退出循环体，故剩下的一个元素需要添加进来
        list1=map(str,list1)#将列表元素的数据类型由整型转化为字符串，才能使用下面的join语句，否则报错
        return ",".join(list1)#返回列表的所有元素，即去掉中括号后的列表
#print(Solution().merge([[18,18],[1,2],[8,10],[4,11],[0,8],[19,22]]))

发表于 2020-09-19 18:13:08 回复(1)