?LeetCode刷題實(shí)戰(zhàn)57：插入?yún)^(qū)間
算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識(shí)和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個(gè)公眾號(hào)后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選 ！
今天和大家聊的問題叫做?插入?yún)^(qū)間，我們先來看題面：
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]]
解釋：這是因?yàn)樾碌膮^(qū)間 [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記錄待插入?yún)^(qū)間
????????l, r = newInterval
????????# 記錄待插入?yún)^(qū)間是否完成插入
????????flag = False
????????
????????for?x, y?in intervals:
????????????# x, y記錄當(dāng)前區(qū)間
????????????# 如果當(dāng)前區(qū)間在待插入?yún)^(qū)間左側(cè)，那么將當(dāng)前區(qū)間插入答案
????????????if?y?< l:
????????????????ret.append([x, y])
????????????# 如果當(dāng)前區(qū)間在待插入?yún)^(qū)間右側(cè)，那么將兩個(gè)區(qū)間都插入答案
????????????elif r < x:
????????????????if?not flag:
????????????????????flag = True
????????????????????ret.append([l, r])
????????????????ret.append([x, y])
????????????# 否則，說明當(dāng)前區(qū)間與待插入?yún)^(qū)間可以合并
????????????# 更新待插入?yún)^(qū)間的范圍
????????????else:
????????????????l, r = min(l, x), max(r, y)
????????# 如果最后還沒有完成插入，說明待插入?yún)^(qū)間大于所有區(qū)間
????????# 手動(dòng)插入，防止遺漏
????????if?not flag:
????????????ret.append([l, r])
????????return?ret
上期推文：