# 57. 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].
```

**Thoughts:**

1. Find the first and last interval index to merge(i,j) and merge them by creating a new interval with (min(*firstInterval*.start, *newInterval*.start), max(*lastInterval*.end, *newInterva*.end), and adding other intervals that is not merged.
   1. To find the first interval: incre i **until** intervals\[i].end > *newInterval*.start
   2. To find the last interval: incre j **until** intervals\[j].start > *newInterval*.end
   3. if i == j == 0; then only need to add \_newinterval \_in front
   4. if i == j == len, then only need to append \_newinterval \_in the end
2. One - Pass: Collect the intervals strictly left or right of the new interval, then merge the new one with the middle ones (if any) before inserting it between left and right ones. [StefanPochmann](https://leetcode.com/stefanpochmann)'s [post](https://leetcode.com/problems/insert-interval/discuss/21622/7+-lines-3-easy-solutions)

**Code**

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

class Solution(object):
    def insert(self, intervals, newInterval):
        """
        :type intervals: List[Interval]
        :type newInterval: Interval
        :rtype: List[Interval]
        """
        res =[]
        i, j, n = 0, 0, len(intervals)
        while i < n:
            if intervals[i].end < newInterval.start:
                res.append(intervals[i])
                i +=1
            else: break

        while j < n:
            if intervals[j].start <= newInterval.end: j += 1
            else: break

        if i == j == 0:
            res.append(newInterval)
            res += intervals
            return res
        elif i == j == n:
            intervals.append(newInterval)
            return intervals

        merge = Interval(min(intervals[i].start, newInterval.start), max(intervals[j - 1].end, newInterval.end))
        res.append(merge)

        for k in range(j, n):
            res.append(intervals[k])
        return res
```

**Code**: Python One pass

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

class Solution(object):
    def insert(self, intervals, newInterval):
        s, e = newInterval.start, newInterval.end
        left, right = [], []
        for i in intervals:
            if i.end < s:
                left += i,
            elif i.start > e:
                right += i,
            else:
                s = min(s, i.start)
                e = max(e, i.end)
        return left + [Interval(s, e)] + right
```