# 436. Find Right Interval

You are given an array of `intervals`, where `intervals[i] = [starti, endi]` and each `starti` is **unique**.

The **right interval** for an interval `i` is an interval `j` such that `startj >= endi` and `startj` is **minimized**. Note that `i` may equal `j`.

Return *an array of **right interval** indices for each interval `i`*. If no **right interval** exists for interval `i`, then put `-1` at index `i`.

 

**Example 1:**

<pre><code><strong>Input: intervals = [[1,2]]
</strong><strong>Output: [-1]
</strong><strong>Explanation: There is only one interval in the collection, so it outputs -1.
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: intervals = [[3,4],[2,3],[1,2]]
</strong><strong>Output: [-1,0,1]
</strong><strong>Explanation: There is no right interval for [3,4].
</strong>The right interval for [2,3] is [3,4] since start0 = 3 is the smallest start that is >= end1 = 3.
The right interval for [1,2] is [2,3] since start1 = 2 is the smallest start that is >= end2 = 2.
</code></pre>

**Example 3:**

<pre><code><strong>Input: intervals = [[1,4],[2,3],[3,4]]
</strong><strong>Output: [-1,2,-1]
</strong><strong>Explanation: There is no right interval for [1,4] and [3,4].
</strong>The right interval for [2,3] is [3,4] since start2 = 3 is the smallest start that is >= end1 = 3.
</code></pre>

&#x20;

**Constraints:**

* `1 <= intervals.length <= 2 * 104`
* `intervals[i].length == 2`
* `-106 <= starti <= endi <= 106`
* The start point of each interval is **unique**.

二分找到end 在sorted starts数组里找位置，第一个大于该end的start

````
```python3
class Solution:
    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
        starts = sorted([(v[0],i) for i,v in enumerate(intervals)])
        res = []
        for s,e in intervals:
            i = bisect.bisect_left(starts,(e,))
            res.append(starts[i][1] if i < len(intervals) else -1)
        return res

        


            
```
````


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nataliekung.gitbook.io/ladder_code/interval/436.-find-right-interval.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.