# 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:**

```
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
```

**Example 2:**

```
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
```

## Analysis

可以看成是Merge Intervals 的follow-up。这一问里*non-overlapping， sorted的前提假设简直就是为了第一问准备的。*

有了前一个问题的解法基础，那么这里的的区别就是在于何时插入新的interval。

因为排过序，用一个循环查找插入位置即可。时间复杂度：O(n)

插入操作java.util.ArrayList.add()，时间复杂度: O(n)

之后再进行Merge Intervals中完全一样的操作即可，时间复杂度：O(n)

空间复杂度，因为有额外的存储最终答案的ArrayList，空间复杂度为: O(n)

## Solution

(13ms, 64%)

```java
/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        List<Interval> ans = new ArrayList<>();

        int index = 0;
        while (index < intervals.size()) {
            if (newInterval.start > intervals.get(index).start) {
                index++;
            } else {
                break;
            }
        }
        intervals.add(index, newInterval);

        Interval last = null;
        for (Interval interval : intervals) {
            if (last == null || interval.start > last.end) {
                ans.add(interval);
                last = interval;
            } else {
                last.end = Math.max(last.end, interval.end);
            }
        }
        return ans;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/sweep-line/insert-interval.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.