# LeetCode 57: Insert Interval

## Problem Restatement

We are given a list of non-overlapping intervals sorted by start time.

Each interval has this form:

```python
[start, end]
```

We are also given one new interval:

```python
newInterval = [start, end]
```

We need to insert `newInterval` into the list so that the final list is still sorted and still has no overlapping intervals. If the new interval overlaps existing intervals, we merge them.

The input intervals are already sorted by start time and already non-overlapping. The official constraints allow `0 <= intervals.length <= 10^4`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A sorted list of non-overlapping intervals and one new interval |
| Output | A sorted list of non-overlapping intervals after insertion |
| Interval format | `[start, end]` |
| Merge rule | Intervals overlap when the next start is less than or equal to the current end |

Function shape:

```python
def insert(intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:
    ...
```

## Examples

For:

```python
intervals = [[1, 3], [6, 9]]
newInterval = [2, 5]
```

The new interval overlaps with `[1, 3]` because:

```python
2 <= 3
```

So we merge them into:

```python
[1, 5]
```

The interval `[6, 9]` does not overlap.

The answer is:

```python
[[1, 5], [6, 9]]
```

For:

```python
intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]]
newInterval = [4, 8]
```

The new interval overlaps with:

```python
[3, 5], [6, 7], [8, 10]
```

They merge into:

```python
[3, 10]
```

The answer is:

```python
[[1, 2], [3, 10], [12, 16]]
```

## First Thought: Add, Sort, and Merge

One simple approach is:

1. Add `newInterval` to `intervals`.
2. Sort all intervals by start time.
3. Use the same merge algorithm from LeetCode 56.

This works, but it ignores an important fact: the original `intervals` list is already sorted and non-overlapping.

Because of that, we can solve the problem in one pass without sorting again.

## Key Insight

The existing intervals fall into three groups:

| Group | Condition | Action |
|---|---|---|
| Before `newInterval` | `interval.end < newInterval.start` | Add directly to answer |
| Overlapping with `newInterval` | `interval.start <= newInterval.end` | Merge into `newInterval` |
| After `newInterval` | `interval.start > newInterval.end` | Add after merged interval |

Because the input is sorted, these groups appear in this exact order.

So we can scan once:

1. Copy all intervals completely before the new interval.
2. Merge all intervals that overlap the new interval.
3. Append the merged new interval.
4. Copy all remaining intervals.

## Algorithm

Use an index `i`.

First, append all intervals that end before the new interval starts:

```python
while i < n and intervals[i][1] < newInterval[0]:
    ans.append(intervals[i])
    i += 1
```

Then merge all overlapping intervals:

```python
while i < n and intervals[i][0] <= newInterval[1]:
    newInterval[0] = min(newInterval[0], intervals[i][0])
    newInterval[1] = max(newInterval[1], intervals[i][1])
    i += 1
```

Append the merged interval:

```python
ans.append(newInterval)
```

Finally, append the rest:

```python
while i < n:
    ans.append(intervals[i])
    i += 1
```

## Correctness

The input intervals are sorted and non-overlapping.

The first loop appends every interval whose end is smaller than the start of `newInterval`. Such intervals cannot overlap with `newInterval`, so they must appear before it in the result.

The second loop processes every interval whose start is less than or equal to the current end of `newInterval`. Each such interval overlaps the new interval, so merging is required. Updating the start with the smaller start and the end with the larger end preserves exactly the union of all overlapping intervals.

When the second loop ends, either all intervals were processed or the next interval starts after the merged interval ends. Therefore the merged interval no longer overlaps anything remaining, so appending it is correct.

All remaining intervals start after the merged interval ends. Since the original list was sorted and non-overlapping, they can be appended unchanged.

Thus the result is sorted, non-overlapping, and covers exactly the original intervals plus the inserted interval.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each interval is visited once |
| Space | `O(n)` | The returned list may contain all intervals |

No sorting is needed.

## Implementation

```python
class Solution:
    def insert(
        self,
        intervals: list[list[int]],
        newInterval: list[int],
    ) -> list[list[int]]:
        ans = []
        i = 0
        n = len(intervals)

        while i < n and intervals[i][1] < newInterval[0]:
            ans.append(intervals[i])
            i += 1

        while i < n and intervals[i][0] <= newInterval[1]:
            newInterval[0] = min(newInterval[0], intervals[i][0])
            newInterval[1] = max(newInterval[1], intervals[i][1])
            i += 1

        ans.append(newInterval)

        while i < n:
            ans.append(intervals[i])
            i += 1

        return ans
```

## Code Explanation

We create the result list and start scanning from the first interval:

```python
ans = []
i = 0
n = len(intervals)
```

First, copy all intervals that come completely before `newInterval`:

```python
while i < n and intervals[i][1] < newInterval[0]:
    ans.append(intervals[i])
    i += 1
```

The condition uses `<`, not `<=`.

If an interval ends at the exact same point where `newInterval` starts, they overlap and must be merged.

Next, merge all overlapping intervals:

```python
while i < n and intervals[i][0] <= newInterval[1]:
```

For every overlap, extend `newInterval`:

```python
newInterval[0] = min(newInterval[0], intervals[i][0])
newInterval[1] = max(newInterval[1], intervals[i][1])
```

After all overlaps are merged, add the final merged interval:

```python
ans.append(newInterval)
```

Then append everything after it:

```python
while i < n:
    ans.append(intervals[i])
    i += 1
```

Finally:

```python
return ans
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.insert([[1, 3], [6, 9]], [2, 5]) == [
        [1, 5],
        [6, 9],
    ]

    assert s.insert(
        [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]],
        [4, 8],
    ) == [
        [1, 2],
        [3, 10],
        [12, 16],
    ]

    assert s.insert([], [5, 7]) == [[5, 7]]

    assert s.insert([[1, 2], [8, 10]], [3, 5]) == [
        [1, 2],
        [3, 5],
        [8, 10],
    ]

    assert s.insert([[3, 5], [7, 9]], [1, 2]) == [
        [1, 2],
        [3, 5],
        [7, 9],
    ]

    assert s.insert([[1, 2], [3, 5]], [6, 7]) == [
        [1, 2],
        [3, 5],
        [6, 7],
    ]

    assert s.insert([[1, 5]], [2, 3]) == [[1, 5]]

    assert s.insert([[1, 5]], [5, 7]) == [[1, 7]]

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[[1,3],[6,9]]`, `[2,5]` | Basic overlap |
| Large example with `[4,8]` | New interval merges multiple intervals |
| Empty intervals | New interval becomes the full answer |
| Insert in the middle | No overlap |
| Insert before all intervals | New interval goes first |
| Insert after all intervals | New interval goes last |
| New interval inside existing interval | Existing interval stays unchanged |
| Touching endpoint | Endpoint contact counts as overlap |