# LeetCode 436: Find Right Interval

## Problem Restatement

We are given a list of intervals.

Each interval is:

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

For each interval `i`, we need to find another interval `j` such that:

```python
intervals[j][0] >= intervals[i][1]
```

In words, interval `j` must start at or after interval `i` ends.

Among all valid intervals, we need the one with the smallest start point.

Return the original index of that interval.

If no such interval exists, return `-1` for that interval.

The problem also says every start point is unique, and `i` may equal `j`. ([leetcode.com](https://leetcode.com/problems/find-right-interval/))

## Input and Output

| Item | Meaning |
|---|---|
| Input | `intervals`, a list of `[start, end]` pairs |
| Output | A list of indices |
| Right interval condition | `start_j >= end_i` |
| Tie rule | Choose the interval with the smallest valid start |
| Missing right interval | Return `-1` |
| Start points | Unique |

Example function shape:

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

## Examples

Example 1:

```python
intervals = [[1, 2]]
```

There is only one interval.

Its end is `2`, but no interval starts at or after `2`.

Answer:

```python
[-1]
```

Example 2:

```python
intervals = [[3, 4], [2, 3], [1, 2]]
```

For `[3, 4]`, we need a start point at least `4`.

No interval has that.

So answer at index `0` is `-1`.

For `[2, 3]`, we need a start point at least `3`.

The interval `[3, 4]` starts at `3`, and its original index is `0`.

So answer at index `1` is `0`.

For `[1, 2]`, we need a start point at least `2`.

The interval `[2, 3]` starts at `2`, and its original index is `1`.

Answer:

```python
[-1, 0, 1]
```

Example 3:

```python
intervals = [[1, 4], [2, 3], [3, 4]]
```

For `[1, 4]`, no interval starts at least `4`.

For `[2, 3]`, the interval `[3, 4]` starts at `3`, so its index is `2`.

For `[3, 4]`, no interval starts at least `4`.

Answer:

```python
[-1, 2, -1]
```

## First Thought: Check Every Interval

For each interval `i`, we can scan every interval `j`.

We check whether:

```python
intervals[j][0] >= intervals[i][1]
```

Among all valid intervals, we keep the one with the smallest start.

This works, but it takes:

```python
O(n^2)
```

because every interval scans all other intervals.

The constraint can be large, so we need a faster lookup.

## Key Insight

For every interval, the only value we search for is:

```python
end_i
```

We need the smallest start point that is greater than or equal to this value.

This is exactly a lower-bound search.

So we can:

1. Store all interval starts with their original indices.
2. Sort them by start.
3. For each interval end, binary search the first start that is at least that end.

For example:

```python
intervals = [[3, 4], [2, 3], [1, 2]]
```

Store starts with original indices:

```python
[(3, 0), (2, 1), (1, 2)]
```

Sort them:

```python
[(1, 2), (2, 1), (3, 0)]
```

Now each query becomes binary search.

## Algorithm

Create an array:

```python
starts = []
```

For each interval at index `i`, append:

```python
(start, i)
```

Sort `starts`.

Create the answer array:

```python
answer = []
```

For each interval `[start, end]`:

1. Binary search in `starts` for the first pair whose start is at least `end`.
2. If found, append that pair’s original index.
3. Otherwise, append `-1`.

Python’s `bisect_left` can do the lower-bound search.

## Correctness

The sorted `starts` array contains every interval start point paired with its original index.

For an interval `i`, a valid right interval must have:

```python
start_j >= end_i
```

Among all such intervals, the required answer is the interval with the smallest possible `start_j`.

Because `starts` is sorted by start point, the first position with start at least `end_i` is exactly the smallest valid start.

Binary search finds exactly this first position.

If such a position exists, the stored original index is the correct answer for interval `i`.

If no such position exists, then every interval starts before `end_i`, so no right interval exists and the correct answer is `-1`.

Applying this independently to every interval gives the correct output array.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n log n)` | Sorting plus one binary search per interval |
| Space | `O(n)` | The sorted start array and answer array |

Here, `n` is the number of intervals.

## Implementation

```python
from bisect import bisect_left

class Solution:
    def findRightInterval(self, intervals: list[list[int]]) -> list[int]:
        starts = []

        for i, (start, end) in enumerate(intervals):
            starts.append((start, i))

        starts.sort()

        answer = []

        for start, end in intervals:
            pos = bisect_left(starts, (end, -1))

            if pos == len(starts):
                answer.append(-1)
            else:
                answer.append(starts[pos][1])

        return answer
```

## Code Explanation

We first collect all starts with their original indices:

```python
starts.append((start, i))
```

This is necessary because sorting changes the order.

Then we sort:

```python
starts.sort()
```

Now the starts are in ascending order.

For each interval, we binary search using its end:

```python
pos = bisect_left(starts, (end, -1))
```

This finds the first pair whose start is at least `end`.

The `-1` is used as the second tuple field. Since original indices are non-negative, `(end, -1)` comes before any tuple `(end, index)`, so it correctly finds the first start equal to `end` when one exists.

If `pos` is outside the array:

```python
if pos == len(starts):
```

then no interval starts at or after `end`, so we append `-1`.

Otherwise, we append the original index stored at that sorted position:

```python
answer.append(starts[pos][1])
```

## Testing

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

    assert s.findRightInterval([[1, 2]]) == [-1]

    assert s.findRightInterval(
        [[3, 4], [2, 3], [1, 2]]
    ) == [-1, 0, 1]

    assert s.findRightInterval(
        [[1, 4], [2, 3], [3, 4]]
    ) == [-1, 2, -1]

    assert s.findRightInterval(
        [[1, 1], [3, 4], [2, 3]]
    ) == [0, -1, 1]

    assert s.findRightInterval(
        [[-10, -5], [-3, 0], [1, 2]]
    ) == [1, 2, -1]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Single interval | Checks missing right interval |
| Sorted backward input | Checks original index recovery |
| Mixed intervals | Checks lower-bound choice |
| Zero-length interval | Checks case where `i` may equal `j` |
| Negative values | Checks binary search with negative starts |