Given a set ofnon-overlappingintervals, 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].

Solution: 先用二分法找list中最后一个元素.end < newOne.start的位置start_pos，list中第一个元素.start > newOne.end的位置end_pos。若end pos == 0，把newOne放在list头；若start pos == list.size() - 1，把newOne放在list尾；否则更新newOne的start和end: newInterval.start = Math.min(newInterval.start, intervals.get(start + 1).start), newInterval.end = Math.max(newInterval.end, intervals.get(end - 1).end)，并把它插在start pos + 1位置，删除被归并的interval

    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        List<Interval> ans = new ArrayList<>();
        if (intervals == null || intervals.size() == 0) {
            ans.add(newInterval);
            return ans;
        }
        int i = 0, j = intervals.size() - 1;
        while (i + 1 < j) {
            int mid = i + (j - i) / 2;
            if (intervals.get(mid).end < newInterval.start) {
                i = mid;
            } else {
                j = mid;
            }
        }
        int start = -1, end = intervals.size();
        if (intervals.get(j).end < newInterval.start) {
            start = j;
        } else if (intervals.get(i).end < newInterval.start) {
            start = i;
        }
        i = 0; j = intervals.size() - 1;
        while (i + 1 < j) {
            int mid = i + (j - i) / 2;
            if (intervals.get(mid).start > newInterval.end) {
                j = mid;
            } else {
                i = mid;
            }
        }
        if (intervals.get(i).start > newInterval.end) {
            end = i;
        } else if (intervals.get(j).start > newInterval.end) {
            end = j;
        }

        if (end == 0) {
            intervals.add(0, newInterval);
            return intervals;
        }
        if (start == intervals.size() - 1) {
            intervals.add(newInterval);
            return intervals;
        }
        newInterval.start = Math.min(newInterval.start, intervals.get(start + 1).start);
        newInterval.end = Math.max(newInterval.end, intervals.get(end - 1).end);

        for (int k = 0; k < intervals.size(); k++) {
            if (k <= start) {
                ans.add(intervals.get(k));
            } else if (k == start + 1) {
                ans.add(newInterval);
            }
            if (k >= end) {
                ans.add(intervals.get(k));
            }
        }
        return ans;
    }