LeetCode Python 排序 合并区间

Leetcode-排序-合并区间

#
# @lc app=leetcode.cn id=56 lang=python3
#
# [56] 合并区间
#
# https://leetcode-cn.com/problems/merge-intervals/description/
#
# algorithms
# Medium (39.12%)
# Likes:    213
# Dislikes: 0
# Total Accepted:    37.1K
# Total Submissions: 94.8K
# Testcase Example:  '[[1,3],[2,6],[8,10],[15,18]]'
#
# 给出一个区间的集合，请合并所有重叠的区间。
# 
# 示例 1:
# 
# 输入: [[1,3],[2,6],[8,10],[15,18]]
# 输出: [[1,6],[8,10],[15,18]]
# 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
# 
# 
# 示例 2:
# 
# 输入: [[1,4],[4,5]]
# 输出: [[1,5]]
# 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

直觉

如果我们按照区间的 start 大小排序，那么在这个排序的列表中可以合并的区间一定是连续的。

算法

首先，我们将列表按上述方式排序。然后，我们将第一个区间插入 merged 数组中，然后按顺序考虑之后的每个区间：如果当前区间的左端点在前一个区间的右端点之后，那么他们不会重合，我们可以直接将这个区间插入 merged 中；否则，他们重合，我们用当前区间的右端点更新前一个区间的右端点 end 如果前者数值比后者大的话。

code-1

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        out=list()
        i=0
        while(i<len(intervals)):
            t_begin = intervals[i][0]
            t_end = intervals[i][1]

            while(i<len(intervals) and intervals[i][0]<=t_end):#区间起点在范围内
                if intervals[i][1]>t_end:#区间终点在范围外，更新区间
                    t_end=intervals[i][1]
                i+=1
            # 完成一个区间
            out.append([t_begin,t_end])
        
        return out

result1

169/169 cases passed (156 ms)
Your runtime beats 23.21 % of python3 submissions
Your memory usage beats 80.31 % of python3 submissions (15.7 MB)

code-2

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key = lambda x:x[0])
        out=list()
        i=0
        while(i<len(intervals)):
            t_begin = intervals[i][0]
            t_end = intervals[i][1]

            while(i<len(intervals) and intervals[i][0]<=t_end):#区间起点在范围内
                if intervals[i][1]>t_end:#区间终点在范围外，更新区间
                    t_end=intervals[i][1]
                i+=1
            # 完成一个区间
            out.append([t_begin,t_end])
        
        return out

result2

169/169 cases passed (108 ms)
Your runtime beats 91.66 % of python3 submissions
Your memory usage beats 63.13 % of python3 submissions (15.8 MB)

总结

看来排序占用时间很多，code1与2的差别只在于，根据前面[0]排序，与[0,1]都排序，时间差距就有40%多