> For the complete documentation index, see [llms.txt](https://lei-d.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lei-d.gitbook.io/leetcode/array/57insert-interval.md).

# 57\_Insert Interval

\[Hard]\[Array, Sort]

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

## Solution 1: Linear Search

**Idea**:

* First search for the position where we should insert or merge the new interval. The intervals on the left will be neglected.
* Then search for the position where we end insertion or merge. The intervals on the right will be neglected.
* Finally insert or merge the new interval.

**Time Complexity**: $$O(n)$$

**Space Complexity**: $$O(1)$$

```python
# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

def insert(intervals, newInterval):
    """
    :type intervals: List[Interval]
    :type newInterval: Interval
    :rtype: List[Interval]
    """
    # sort the intervals by starting point
    # intervals.sort(key=lambda x: x.start)

    # search the position to start insert/merge
    i = 0
    while i < len(intervals) and newInterval.start > intervals[i].end:
        i += 1
    # if the starting point of new interval is larger than every interval
    # insert new interval to the end
    if i == len(intervals):
        return intervals + [newInterval]

    # search the position to finish insert/merge
    j = i
    while j < len(intervals) and newInterval.end >= intervals[j].start:
        j += 1

    if j == i:
        # insert the new interval
        intervals[i:j] = [newInterval]
    else:
        # merge the new interval with overlapping intervals
        left = min(intervals[i].start, newInterval.start)
        right = max(intervals[j-1].end, newInterval.end)
        # insert into the intervals
        intervals[i:j] = [Interval(left, right)]
    return intervals
```

## Solution 2: Binary Search

**Idea**:

* Extract all the starting values from the intervals, find the right place to insert the starting point in the new interval by binary search
* Extract all the ending values from the intervals, find the right place to insert the ending point in the new interval bu binary search
* Insert or merge the new interval into the overlapping place.

**Time Complexity**: $$O(\log{n})$$

**Space Complexity**: $$O(1)$$

```python
# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

def insert(intervals, newInterval):
    """
    :type intervals: List[Interval]
    :type newInterval: Interval
    :rtype: List[Interval]
    """        
    left, right = newInterval.start, newInterval.end
    start = [interval.start for interval in intervals]
    end = [interval.end for interval in intervals]
    i = bisect.bisect_left(start, left)
    j = bisect.bisect(end, right)
    if i > 0 and left <= intervals[i-1].end:
        left = intervals[i-1].start
        i = i - 1
    if j < len(intervals) and right >= intervals[j].start:
        right = intervals[j].end
        j = j + 1
    intervals[i:j] = [Interval(left, right)]
    return intervals
```