# 436. Find Right Interval

## Medium

***

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

**Example 2:**

<pre><code>Input: intervals = [[3,4],[2,3],[1,2]]
<strong>Output:
</strong> [-1,0,1]
<strong>Explanation:
</strong> There is no right interval for [3,4].
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>Input: intervals = [[1,4],[2,3],[3,4]]
<strong>Output:
</strong> [-1,2,-1]
<strong>Explanation:
</strong> There is no right interval for [1,4] and [3,4].
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**.