### 问题描述

https://leetcode.com/problems/insert-interval/#/description

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.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

### 算法

1. newIntervalit前面，表现为newInterval.end < it.start，此时先添加newInterval，后添加it，因为newInterval已经添加进去了，所以后面的就无需比较了
2. newIntervalit后面，表现为newInterval.start > it.end，此时只添加it到结果数组中即可，让newInterval再与后面的去比较
3. 两者有重叠部分，需要合并，将it合并到newInterval

### 代码

public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
List<Interval> res = new ArrayList<>();
boolean hasInserted = false; // 是否已插入newInterval
for(Interval it:intervals) {
if(hasInserted || it.end < newInterval.start) {
} else if(it.start > newInterval.end) {
hasInserted = true;
} else {
newInterval.start = Math.min(newInterval.start, it.start);
newInterval.end = Math.max(newInterval.end, it.end);
}
}
if(!hasInserted) {