「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每日一题」——836. 矩形重叠
836. 矩形重叠 链接：https://leetcode-cn.com/problems/rectangle-overlap/难度：简单 题目 矩形以列表 [x1, y1, x2…
-
「LeetCode每日一题」—— 33. 搜索旋转排序数组
33. 搜索旋转排序数组 链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array/难度：中等 题目 点…
-
「LeetCode每日一题」——LCOF.62. 圆圈中最后剩下的数字
LCOF.62. 圆圈中最后剩下的数字 链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-…
-
「LeetCode每日一题」——LCOF.59 – II. 队列的最大值
链接：https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/难度：中等 题目 请定义一个队列并实现函数 max_v…
-
「LeetCode每日一题」—— LCOF.13. 机器人的运动范围
LCOF.13. 机器人的运动范围 题目链接：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof…
-
「LeetCode每日一题」——LCCI. 01.06 字符串压缩
LCCI. 01.06 字符串压缩 链接：https://leetcode-cn.com/problems/compress-string-lcci/难度：简单 题目 字符串压缩。…
-
「LeetCode每日一题」—— 8. 字符串转换整数 (atoi)
8. 字符串转换整数 (atoi) 链接：https://leetcode-cn.com/problems/string-to-integer-atoi/难度：中等 题目 请你来实…
-
「LeetCode每日一题」——1162. 地图分析
1162. 地图分析 链接：https://leetcode-cn.com/problems/as-far-from-land-as-possible/难度：中等 题目 你现在手里…
-
「LeetCode每日一题」—— 200. 岛屿数量
200. 岛屿数量 链接：https://leetcode-cn.com/problems/number-of-islands/难度：中等 思路 这题比较简单，思路就是DFS。 我…
-
「LeetCode每日一题」225. 用队列实现栈
LeetCode每日一题 周五跟大家预告了LeetCode每日一题的活动，今天活动已经开始了。打开leetcode中文版，你可以在题库中看到制定的题目，行动起来吧。 在这里帖下打卡…
您必须登录才能发表评论。