# LeetCode 56: Merge Intervals

## Problem Restatement

We are given an array of intervals.

Each interval has a start and an end:

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

We need to merge all overlapping intervals and return a list of non-overlapping intervals that covers the same ranges as the original input.

Two intervals overlap when the next interval starts before or exactly when the current interval ends.

For example:

```python
[1, 4] and [4, 5]
```

These overlap because they touch at `4`, so they merge into:

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

The official constraints are `1 <= intervals.length <= 10^4`, `intervals[i].length == 2`, and `0 <= start_i <= end_i <= 10^4`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A list of intervals |
| Output | A list of merged non-overlapping intervals |
| Interval format | `[start, end]` |
| Overlap rule | `[a, b]` overlaps `[c, d]` when `c <= b` after sorting |

Function shape:

```python
def merge(intervals: list[list[int]]) -> list[list[int]]:
    ...
```

## Examples

For:

```python
intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
```

The intervals `[1, 3]` and `[2, 6]` overlap because:

```python
2 <= 3
```

So they merge into:

```python
[1, 6]
```

The intervals `[8, 10]` and `[15, 18]` do not overlap with anything.

The answer is:

```python
[[1, 6], [8, 10], [15, 18]]
```

For:

```python
intervals = [[1, 4], [4, 5]]
```

The two intervals touch at endpoint `4`, so they count as overlapping.

The answer is:

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

## First Thought: Compare Every Pair

A direct approach is to compare every interval with every other interval.

If two intervals overlap, merge them. Then repeat until no more intervals can be merged.

This is difficult to implement cleanly because merging one pair can create a new interval that overlaps with another pair. We may need many passes.

There is a simpler approach if we first sort the intervals.

## Key Insight

Sort intervals by start time.

After sorting, any interval that can overlap the current merged interval must appear next to it or later in the list.

So we can scan from left to right and maintain the last merged interval.

For each new interval `[start, end]`:

1. If `start` is greater than the end of the last merged interval, there is no overlap.
2. Otherwise, the intervals overlap, so extend the last merged interval.

The merge rule is:

```python
merged[-1][1] = max(merged[-1][1], end)
```

Why `max` is needed:

```python
[1, 10] and [2, 3]
```

These overlap, but the merged end should stay `10`.

## Algorithm

Sort the intervals:

```python
intervals.sort(key=lambda x: x[0])
```

Create an empty result list:

```python
merged = []
```

For each interval:

1. If `merged` is empty, append the interval.
2. Otherwise, compare the current interval with the last merged interval.
3. If the current interval starts after the last merged interval ends, append it.
4. Otherwise, merge it by updating the last end.

Return `merged`.

## Correctness

After sorting, intervals are processed in nondecreasing order of start time.

The algorithm keeps `merged` as a list of non-overlapping intervals that covers all intervals processed so far.

When the next interval starts after the end of the last merged interval, it cannot overlap that last interval. Since all future intervals start at the same position or later, this interval should begin a new merged range. Appending it is correct.

When the next interval starts before or exactly at the end of the last merged interval, the two intervals overlap. Their union is covered by keeping the same start and updating the end to the larger of both ends. This preserves coverage and keeps the result non-overlapping.

By processing every interval once after sorting, the algorithm covers every input interval and merges exactly the overlapping ones. Therefore the returned intervals are correct.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n log n)` | Sorting dominates the runtime |
| Space | `O(n)` | The output list may store all intervals when none overlap |

Depending on the sorting implementation, sorting may also use extra space.

## Implementation

```python
class Solution:
    def merge(self, intervals: list[list[int]]) -> list[list[int]]:
        intervals.sort(key=lambda x: x[0])

        merged = []

        for start, end in intervals:
            if not merged or start > merged[-1][1]:
                merged.append([start, end])
            else:
                merged[-1][1] = max(merged[-1][1], end)

        return merged
```

## Code Explanation

First, sort intervals by their start:

```python
intervals.sort(key=lambda x: x[0])
```

This makes overlapping intervals appear close together.

Then create the answer list:

```python
merged = []
```

For each interval:

```python
for start, end in intervals:
```

If `merged` is empty, we add the first interval.

If the current interval starts after the last merged interval ends, there is no overlap:

```python
if not merged or start > merged[-1][1]:
    merged.append([start, end])
```

Otherwise, the intervals overlap.

We extend the last merged interval:

```python
merged[-1][1] = max(merged[-1][1], end)
```

Finally, return the merged list:

```python
return merged
```

## Testing

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

    assert s.merge([[1, 3], [2, 6], [8, 10], [15, 18]]) == [
        [1, 6],
        [8, 10],
        [15, 18],
    ]

    assert s.merge([[1, 4], [4, 5]]) == [[1, 5]]

    assert s.merge([[1, 4]]) == [[1, 4]]

    assert s.merge([[1, 4], [0, 2], [3, 5]]) == [[0, 5]]

    assert s.merge([[1, 10], [2, 3], [4, 8]]) == [[1, 10]]

    assert s.merge([[1, 2], [3, 4], [5, 6]]) == [
        [1, 2],
        [3, 4],
        [5, 6],
    ]

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[[1,3],[2,6],[8,10],[15,18]]` | Standard overlapping example |
| `[[1,4],[4,5]]` | Touching endpoints count as overlap |
| `[[1,4]]` | Single interval |
| `[[1,4],[0,2],[3,5]]` | Input starts unsorted |
| `[[1,10],[2,3],[4,8]]` | Smaller intervals inside a larger one |
| `[[1,2],[3,4],[5,6]]` | No intervals overlap |