# 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.

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].

### 代码​

// Insert Interval// 时间复杂度O(n)，空间复杂度O(1)public class Solution {    public int[][] insert(int[][] intervals, int[] newInterval) {        ArrayList<int[]> list = new ArrayList<>(Arrays.asList(intervals));        insert(list, newInterval);        return list.toArray(new int[0][2]);    }    private void insert(ArrayList<int[]> intervals, int[] newInterval) {        for (int i = 0; i < intervals.size();) {            final int[] cur = intervals.get(i);            if (newInterval[1] < cur[0]) {                intervals.add(i, newInterval);                return;            } else if (newInterval[0] > cur[1]) {                ++i;            } else {                newInterval[0] = Math.min(newInterval[0], cur[0]);                newInterval[1] = Math.max(newInterval[1], cur[1]);                intervals.remove(i);            }        }        intervals.add(newInterval);    }}