LeetCode刷题实战57：插入区间
共 2002字，需浏览 5分钟
·
2020-10-06 01:42
算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
今天和大家聊的问题叫做 插入区间，我们先来看题面：
https://leetcode-cn.com/problems/insert-interval/
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
题意
样例
示例 1：
输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]
示例 2：
输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
解题
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
ret = []
# l, r记录待插入区间
l, r = newInterval
# 记录待插入区间是否完成插入
flag = False
for x, y in intervals:
# x, y记录当前区间
# 如果当前区间在待插入区间左侧，那么将当前区间插入答案
if y < l:
ret.append([x, y])
# 如果当前区间在待插入区间右侧，那么将两个区间都插入答案
elif r < x:
if not flag:
flag = True
ret.append([l, r])
ret.append([x, y])
# 否则，说明当前区间与待插入区间可以合并
# 更新待插入区间的范围
else:
l, r = min(l, x), max(r, y)
# 如果最后还没有完成插入，说明待插入区间大于所有区间
# 手动插入，防止遗漏
if not flag:
ret.append([l, r])
return ret
上期推文：