# LeetCode 986: Interval List Intersections

## Problem Restatement

We are given two lists of closed intervals:

```python
firstList
secondList
```

Each list is sorted, and intervals inside the same list do not overlap.

We need to return all intersections between intervals from the two lists.

A closed interval `[a, b]` includes both endpoints. So `[1, 5]` and `[5, 10]` intersect at `[5, 5]`.

The official constraints allow both lists to have length up to `1000`, and each list is sorted with pairwise disjoint intervals.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Two sorted interval lists |
| Output | List of all interval intersections |
| Interval type | Closed interval `[start, end]` |
| Important detail | Touching endpoints count as an intersection |

Function shape:

```python
def intervalIntersection(
    firstList: list[list[int]],
    secondList: list[list[int]],
) -> list[list[int]]:
    ...
```

## Examples

Example 1:

```python
firstList = [[0,2],[5,10],[13,23],[24,25]]
secondList = [[1,5],[8,12],[15,24],[25,26]]
```

The intersections are:

| First interval | Second interval | Intersection |
|---|---|---|
| `[0, 2]` | `[1, 5]` | `[1, 2]` |
| `[5, 10]` | `[1, 5]` | `[5, 5]` |
| `[5, 10]` | `[8, 12]` | `[8, 10]` |
| `[13, 23]` | `[15, 24]` | `[15, 23]` |
| `[24, 25]` | `[15, 24]` | `[24, 24]` |
| `[24, 25]` | `[25, 26]` | `[25, 25]` |

Answer:

```python
[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
```

Example 2:

```python
firstList = [[1,3],[5,9]]
secondList = []
```

There are no intervals in `secondList`, so there can be no intersections.

Answer:

```python
[]
```

## First Thought: Compare Every Pair

The direct solution is to compare every interval from `firstList` with every interval from `secondList`.

For two intervals:

```python
[a_start, a_end]
[b_start, b_end]
```

their intersection starts at the later start:

```python
start = max(a_start, b_start)
```

and ends at the earlier end:

```python
end = min(a_end, b_end)
```

If:

```python
start <= end
```

then they overlap.

```python
class Solution:
    def intervalIntersection(
        self,
        firstList: list[list[int]],
        secondList: list[list[int]],
    ) -> list[list[int]]:
        answer = []

        for a_start, a_end in firstList:
            for b_start, b_end in secondList:
                start = max(a_start, b_start)
                end = min(a_end, b_end)

                if start <= end:
                    answer.append([start, end])

        return answer
```

This is correct, but it ignores the sorted structure of the input.

## Problem With Comparing Every Pair

If `firstList` has `m` intervals and `secondList` has `n` intervals, comparing every pair costs:

```python
O(m * n)
```

Both lists are already sorted and disjoint internally, so we can scan them more efficiently.

## Key Insight

Use two pointers.

Let:

```python
i = current interval in firstList
j = current interval in secondList
```

At each step, compare:

```python
firstList[i]
secondList[j]
```

Their overlap, if it exists, is:

```python
[max(start1, start2), min(end1, end2)]
```

After processing this pair, move the pointer whose interval ends earlier.

Why?

Suppose:

```python
end1 < end2
```

Then `firstList[i]` ends before `secondList[j]`.

Because `secondList` is sorted and disjoint, future intervals in `secondList` start after `secondList[j]` ends. So `firstList[i]` cannot overlap any later interval from `secondList`.

It is safe to move `i`.

## Algorithm

Initialize:

```python
i = 0
j = 0
answer = []
```

While both pointers are inside their lists:

1. Read the current intervals.
2. Compute the possible intersection:
   ```python id="h6uw69"
   start = max(start1, start2)
   end = min(end1, end2)
   ```
3. If `start <= end`, append `[start, end]`.
4. If `end1 < end2`, move `i`.
5. Otherwise, move `j`.

Return `answer`.

## Correctness

At every step, the algorithm compares the earliest unprocessed interval from `firstList` with the earliest unprocessed interval from `secondList`.

For the current pair, the intersection is exactly:

```python
[max(start1, start2), min(end1, end2)]
```

If the computed start is less than or equal to the computed end, the intervals share that closed interval. If not, they do not overlap.

After checking the pair, the algorithm advances the interval with the smaller end.

If `firstList[i]` ends before `secondList[j]`, then `firstList[i]` cannot intersect any later interval in `secondList`, because later intervals in `secondList` start after the current `secondList[j]`. So advancing `i` cannot skip any valid intersection.

The same argument applies when `secondList[j]` ends first.

Thus every possible intersection is considered before either interval involved becomes impossible to intersect future intervals. The algorithm appends exactly the valid intersections, so the returned list is correct.

## Complexity

Let `m = len(firstList)` and `n = len(secondList)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(m + n)` | Each pointer only moves forward |
| Space | `O(1)` | Extra working space is constant, ignoring the output |

The output itself can contain up to `O(m + n)` intervals.

## Implementation

```python
class Solution:
    def intervalIntersection(
        self,
        firstList: list[list[int]],
        secondList: list[list[int]],
    ) -> list[list[int]]:
        i = 0
        j = 0
        answer = []

        while i < len(firstList) and j < len(secondList):
            start1, end1 = firstList[i]
            start2, end2 = secondList[j]

            start = max(start1, start2)
            end = min(end1, end2)

            if start <= end:
                answer.append([start, end])

            if end1 < end2:
                i += 1
            else:
                j += 1

        return answer
```

## Code Explanation

We keep one pointer for each interval list:

```python
i = 0
j = 0
```

The loop continues while both lists still have intervals:

```python
while i < len(firstList) and j < len(secondList):
```

Read the current intervals:

```python
start1, end1 = firstList[i]
start2, end2 = secondList[j]
```

Compute their possible overlap:

```python
start = max(start1, start2)
end = min(end1, end2)
```

If the overlap is non-empty, store it:

```python
if start <= end:
    answer.append([start, end])
```

Then advance the interval that ends earlier:

```python
if end1 < end2:
    i += 1
else:
    j += 1
```

When either list is exhausted, no more intersections are possible.

## Testing

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

    assert s.intervalIntersection(
        [[0,2],[5,10],[13,23],[24,25]],
        [[1,5],[8,12],[15,24],[25,26]],
    ) == [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

    assert s.intervalIntersection(
        [[1,3],[5,9]],
        [],
    ) == []

    assert s.intervalIntersection(
        [],
        [[4,8]],
    ) == []

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

    assert s.intervalIntersection(
        [[1,5]],
        [[5,10]],
    ) == [[5,5]]

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| Standard example | `[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]` | Multiple overlaps |
| `[[1,3],[5,9]]`, `[]` | `[]` | Empty second list |
| `[]`, `[[4,8]]` | `[]` | Empty first list |
| `[[1,7]]`, `[[3,5]]` | `[[3,5]]` | One interval fully contains another |
| `[[1,5]]`, `[[5,10]]` | `[[5,5]]` | Closed intervals can touch at one point |