# LeetCode: 57. 插入区间¶

## 1、题目描述¶

输入: intervals = [[1,3],[6,9]], newInterval = [2,5]



输入: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]



## 2、解题思路¶

• 判断需要插入还是需要合并

• 采用二分查找找到对应的位置

• 然后判断与前后区间是否有交叉，有交叉则进行合并
• 无交叉直接插入
from typing import List
import bisect

class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
x, y = newInterval
length = len(intervals)

if not intervals:
return [[x, y]]

left = bisect.bisect_left(intervals, [x, x])
if left == 0:
if y < intervals[0][0]:
return [[x, y]] + intervals
start = min(x, intervals[left][0])

elif left >= length:
if x > intervals[left - 1][1]:
return intervals + [[x, y]]
left -= 1
start = min(x, intervals[left][0])

else:
if x > intervals[left - 1][1] and y < intervals[left][0]:
intervals.insert(left, [x, y])
return intervals
if x <= intervals[left - 1][1]:
left -= 1
start = min(x, intervals[left][0])

if y < intervals[0][0]:
return [[x, y]] + intervals

if left and x > intervals[left - 1][1] and left < length - 1 and y < intervals[left][0]:
intervals.insert(left, [x, y])
return intervals

right = left
while right < length - 1 and y >= intervals[right + 1][0]:
right += 1
end = max(y, intervals[right][1])
intervals[left:right + 1] = [[start, end]]

return intervals