【python-leetcode56-区间合并】合并区间

概述问题描述： 给出一个区间的集合，请合并所有重叠的区间。 示例 1: 输入: [[1,3],[2,6],[8,10],[15,18]]输出: [[1,6],[8,10],[15,18]]解释: 区间 [

问题描述：

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

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,18]]
解释: 区间 [1,3] 和 [2,6] 重叠,将它们合并为 [1,6].
示例 2:

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

这题之间看过，今天又看到了，大致知道是先要排序，但是忘了怎么更新结果。

核心：其实是贪心法的体现，关注于相邻的两个数组，那么就有两种情况，以[[1,18]]为例。

先对二维数组按一维数组的第0位进行排序，假设结果是res=[]。

当res为空时先将[1,3]加入到res中，再遍历到[2,6]，此时有两种情况，如果当前数组的第0位大于res中最后一个数组的第1位，说明当前数组和res末尾的数组不会重叠，此时之间将当前数组加到res末尾。如果当前数组第0位小于或等于res末尾数组第1位，再判断当前数组第1位和res末尾数组第一位誰大，将其更新res末尾数组的第一位。依次类推。

代码：

class Solution:    def merge(self,intervals: List[List[int]]) -> List[List[int]]:        res = []        intervals.sort()        for i in intervals:            if not res or res[-1][1]<i[0]:                res.append(i)            else:                res[-1] = max(res[-1],i[1])        return res

结果：

总结

以上是内存溢出为你收集整理的【python-leetcode56-区间合并】合并区间全部内容，希望文章能够帮你解决【python-leetcode56-区间合并】合并区间所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。