首页 > 试题广场 >

合并区间

[编程题]合并区间

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

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

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

数据范围：区间组数 $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]]

算法知识视频讲解

查看答案及解析

Python3

LeoAlan

# @param intervals Interval类一维数组
# @return Interval类一维数组

# 解法一
class Solution:
    # intervals为一list，该list包含多个Interval类，每个Interval类有start和end两个属性，表示一个区间
    def merge(self, intervals: List[Interval]) -> List[Interval]:
        # 如果intervals为空，返回空list
        if not intervals:
            return []
        # 按照start属性对intervals进行排序，使用了lambda表达式
        intervals = sorted(intervals, key=lambda x: x.start)

        # 初始化结果list，将intervals的第一个元素加入结果list
        res = [intervals[0]]

        # 遍历intervals，如果新区间的start小于等于最后一个区间的end；且新区间的end大于最后一个区间的end，说明两个区间有重叠，将res的最后一个区间的end更新为新区间的end

        # 如果当前区间的start大于res的最后一个区间的end，说明两个区间没有重叠，将当前区间加入res

        for i in intervals:
            if i.start <= res[-1].end and i.end > res[-1].end:
                res[-1].end = i.end
            elif i.start > res[-1].end:
                res.append(i)
        return res

# 解法二
class Solution:
    # intervals为一list，该list包含多个Interval类，每个Interval类有start和end两个属性，表示一个区间
    def merge(self, intervals: List[Interval]) -> List[Interval]:
        # 如果intervals为空，返回空list
        if not intervals:
            return []
        # 按照start属性对intervals进行排序，使用了lambda表达式
        intervals = sorted(intervals, key=lambda x: x.start)

        # 初始化结果list，将intervals的第一个元素加入结果list
        res = [intervals[0]]

        # 遍历intervals，如果新区间的start小于等于最后一个区间的end，说明两个区间有重叠，将res的最后一个区间的end更新为值较大的end

        # 如果当前区间的start大于res的最后一个区间的end，说明两个区间没有重叠，将当前区间加入res

        for i in intervals:
            if i.start <= res[-1].end:
                res[-1].end = max(i.end,res[-1].end)
            else:
                res.append(i)
        return res

发表于 2023-09-16 22:18:32 回复(0)

Python3

glennbh

如果是练手自己实现排序，用快速排序会超时，用归并排序可以通过。

是因为快速排序在极限情况（本来就排好）下时间复杂度是O(N2)，而归并排序因为是一直做二分，所以复杂度稳定的为O(NlogN)。但归并排序需要空间复杂度为O(n)，而快速排序空间复杂度为O(1)。具体见https://zhuanlan.zhihu.com/p/95080265

class Solution:
    def merge(self , intervals: List[Interval]) -> List[Interval]:
        # write code here
        if len(intervals) <= 1:
            return intervals

        # sort
        # intervals.sort(key=lambda x:x.start)

        self.mergeSortIntervalList(intervals, 0, len(intervals)-1)
        # self.quickSortIntervalList(intervals, 0, len(intervals)-1)

        # merge
        result = [intervals[0]]
        for ind in range(1, len(intervals)):
            if intervals[ind].start <= result[-1].end:
                result[-1].end = max(intervals[ind].end, result[-1].end)
            else:
                result.append(intervals[ind])

        return result

    def quickSortIntervalList(self , intervals: List[Interval], bleft: int, bright: int):
        if bleft >= bright:
            return

        left = bleft
        right = bright
        point = intervals[left]
        while left < right:
            while left < right and intervals[right].start >= point.start:
                right -= 1
            intervals[left] = intervals[right]

            while left < right and intervals[left].start <= point.start:
                left += 1
            intervals[right] = intervals[left]

        intervals[left] = point
        self.quickSortIntervalList(intervals, bleft, left-1)
        self.quickSortIntervalList(intervals, left+1, bright)

    def mergeSortIntervalList(self , intervals: List[Interval], left: int, right: int):
        if left < right:
            middle = int((left + right) / 2)
            self.mergeSortIntervalList(intervals, left, middle)
            self.mergeSortIntervalList(intervals, middle+1, right)
            self.mergeSortCores(intervals, left, middle, right)


    def mergeSortCores(self , intervals: List[Interval], left: int, middle: int, right: int):
        i = left
        j = middle+1
        tmp = []
        while i <= middle and j <= right:
            if intervals[i].start <= intervals[j].start:
                tmp.append(intervals[i])
                i += 1
            else:
                tmp.append(intervals[j])
                j += 1

        while i <= middle:
            tmp.append(intervals[i])
            i += 1

        while j <= right:
            tmp.append(intervals[j])
            j += 1

        for ind in range(len(tmp)):
            intervals[left+ind] = tmp[ind]

发表于 2023-01-19 15:13:48 回复(0)

Python3

JianYue

# 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: List[Interval]) -> List[Interval]:
        length = len(intervals)
        if length <= 1:
            return intervals
        par1 = self.merge(intervals[0:length//2])
        par2 = self.merge(intervals[length//2:length])
        ret = []
        tmp = None
        while par1 and par2:
            node = None
            if par1[0].start > par2[0].start:
                node = par2.pop(0)
            else:
                node = par1.pop(0)
            if tmp:
                if tmp.start <= node.start <= tmp.end:
                    tmp.end = max(tmp.end, node.end)
                elif node.start <= tmp.start <= node.end:
                    tmp.start = node.start
                    tmp.end = max(tmp.end, node.end)
                else:
                    ret.append(tmp)
                    tmp = node
            else:
                tmp = node
        par = par1 if par1 else par2
        for i in par:
            if i.start > tmp.end:
                ret.append(tmp)
                tmp = i
            else:
                tmp.end = max(tmp.end, i.end)
        ret.append(tmp)
        return ret

发表于 2022-09-24 13:56:04 回复(0)

Python3

Vivimore

class Solution:
    def merge(self , intervals: List[Interval]) -> List[Interval]:
        if not intervals:
            return []
        intervals.sort(key=lambda x: x.start)
        res = [intervals[0]]
        for i in intervals[1:]:
            if res[-1].end < i.start:
                res.append(i)
            elif res[-1].end < i.end:
                res[-1].end = i.end
        return res

发表于 2022-05-26 20:59:39 回复(0)

Python3

Joy_9

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals=sorted(intervals,key=lambda x:x[0])
        def me(intervals):
            if len(intervals) <= 1:
                return intervals
            mid = len(intervals) // 2
            left = me(intervals[:mid])
            right = me(intervals[mid:])
            res = []
            while len(left) > 0 and len(right) > 0:
                a = left.pop(-1)
                b = right.pop(0)
                if a[1] >= b[0]:
                    res.append([a[0], max(a[1],b[1])])
              
                else:
                    res.append(a)
                    res.append(b)
            if len(left) > 0:
                res.extend(left)
            else:
                res.extend(right)
            return sorted(res,key=lambda x:x[0])
        v1=me(intervals)
        v2=me(v1)
        while v1!=v2:
            v2=v1
            v1=me(v2)
            
        return v1

发表于 2022-01-15 06:09:19 回复(0)

Python3

牛客38477449号

class Solution:
    def merge(self , intervals ):
        # write code here
        if len(intervals) == 1:
            return intervals
        intervals = sorted(intervals, key=lambda x: (x.start, x.end))
        intervals.append(Interval(10001, 10001))
        res = []
        temp = intervals[0]
        for i in range(1, len(intervals)):
            if intervals[i].start <= temp.end:
                temp.end = max(intervals[i].end, temp.end)
            else:
                res.append(temp)
                temp = intervals[i]
        return res

发表于 2021-12-24 21:34:50 回复(0)

Python3

云云云小雀

class Solution:
    
    def merge(self , intervals ):
        # write code here
        
        intervals.sort(key=(lambda elme:elme.start))
        res = []
        for i in range (len(intervals)):
            if res == []:
                res.append(intervals[i])
            else:
                if res[-1].end >= intervals[i].start :
                    res[-1].end = max(intervals[i].end, res[-1].end)
                else:
                    res.append(intervals[i])
        return res

发表于 2021-09-02 00:31:11 回复(0)