「LeetCode每日一题」—— 56. 合并区间
56. 合并区间
链接：https://leetcode-cn.com/problems/merge-intervals/
难度：中等
题目
给出一个区间的集合，请合并所有重叠的区间。
示例 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] 可被视为重叠区间。
思路
先分析一下题意，我们来看例子：
输入：[[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
因为[1,3],[2,6] 是重叠的，可以合并为[1,6]。
我们可以先做一个按照区间第一个值做排序，然后看哪些区间是可以合并的（右边界比新加入的左边界大，这个例子中3比2大）如果重合，右边界更新为新加入区间的右边界就可以了。
代码见解决方案
方案代码
解决方案：
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key=lambda x: x[0])
ans = []
for interval in intervals:
if not ans or ans[-1][1] < interval[0]:
ans.append(interval)
else:
ans[-1][1] = max(ans[-1][1], interval[1])
return ans原创文章，作者：flypython，如若转载，请注明出处：http://flypython.com/algorithm/leetcode/331.html
微信扫一扫 
支付宝扫一扫 相关推荐
-
「LeetCode每日一题」—— 199. 二叉树的右视图
199. 二叉树的右视图 链接：https://leetcode-cn.com/problems/binary-tree-right-side-view/难度：中等 题目 点击原文…
-
「LeetCode每日一题」—— 11. 盛最多水的容器
11. 盛最多水的容器 链接：https://leetcode-cn.com/problems/container-with-most-water/难度：中等 题目 思路 这道题和…
-
「LeetCode每日一题」—— 55. 跳跃游戏
55. 跳跃游戏 链接：https://leetcode-cn.com/problems/jump-game/难度：中等 题目 思路 这题很容易想到从后面开始往前面跳。如果倒数第一…
-
「LeetCode每日一题」—— 466. 统计重复个数
466. 统计重复个数 链接：https://leetcode-cn.com/problems/count-the-repetitions/难度：困难 题目 思路 这是一道困难题，…
-
「LeetCode每日一题」——LCCI 10.01. 合并排序的数组
LCCI 10.01. 合并排序的数组 链接：https://leetcode-cn.com/problems/sorted-merge-lcci/难度：简单 题目 给定两个排序后…
-
「LeetCode每日一题」—— 542. 01 矩阵
542. 01 矩阵 链接：https://leetcode-cn.com/problems/01-matrix/难度：中等 题目 点击原文链接跳转查看题目 思路 这道题求的就是每…
-
「LeetCode每日一题」——914. 卡牌分组
914. 卡牌分组 链接：https://leetcode-cn.com/problems/x-of-a-kind-in-a-deck-of-cards/难度：简单 题目 给定一副…
-
「LeetCode每日一题」—— 200. 岛屿数量
200. 岛屿数量 链接：https://leetcode-cn.com/problems/number-of-islands/难度：中等 思路 这题比较简单，思路就是DFS。 我…
-
「LeetCode每日一题」—— 23. 合并K个排序链表
23. 合并K个排序链表 链接：https://leetcode-cn.com/problems/merge-k-sorted-lists/难度：中等 题目 点击原文链接跳转查看题…
-
「LeetCode每日一题」—— 8. 字符串转换整数 (atoi)
8. 字符串转换整数 (atoi) 链接：https://leetcode-cn.com/problems/string-to-integer-atoi/难度：中等 题目 请你来实…
您必须登录才能发表评论。