Algorithm

Problem Name: 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:

```Input: intervals = [[1,2]]
Output: [-1]
Explanation: There is only one interval in the collection, so it outputs -1.
```

Example 2:

```Input: intervals = [[3,4],[2,3],[1,2]]
Output: [-1,0,1]
Explanation: 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.
```

Example 3:

```Input: intervals = [[1,4],[2,3],[3,4]]
Output: [-1,2,-1]
Explanation: 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.
```

Constraints:

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

Code Examples

#1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
vector<int> findRightInterval(vector < Interval>& intervals) {
vector<int>res;
map < int, int>m;
for(int i = 0; i  <  intervals.size(); i++) m[intervals[i].start] = i;
for(auto i: intervals){
auto p = m.lower_bound(i.end);
res.push_back(p == m.end() ? -1 : (*p).second);
}
return res;
}
};
``````
Copy The Code &

Input

cmd
intervals = [[1,2]]

Output

cmd
[-1]

#2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int[] findRightInterval(int[][] intervals) {
TreeMap();
for (int i = 0; i  <  intervals.length; i++) {
map.computeIfAbsent(intervals[i][0], k -> new PriorityQueue<>(
Comparator.comparingInt(o -> intervals[o][0]))
}
int[] ans = new int[intervals.length];
Arrays.fill(ans, -1);
for (int i = 0; i  <  intervals.length; i++) {
Integer upper = map.ceilingKey(intervals[i][1]);
if (upper != null) {
ans[i] = map.get(upper).peek();
}
}
return ans;
}
}
``````
Copy The Code &

Input

cmd
intervals = [[1,2]]

Output

cmd
[-1]

#3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const findRightInterval = function(intervals) {
const res = []
const arrary = intervals
.map((interval, idx) => ({ interval, idx }))
.sort((obj1, obj2) => obj1.interval[0] - obj2.interval[0])
for (let interval of intervals) {
const val = interval[interval.length - 1]
let left = 0,
right = intervals.length
while (left < right) {
const mid = Math.floor((left + right) / 2)
if (arrary[mid].interval[0] >= val) {
right = mid
} else {
left = mid + 1
}
}
if (left >= intervals.length) {
res.push(-1)
} else {
res.push(arrary[left].idx)
}
}
return res
}
``````
Copy The Code &

Input

cmd
intervals = [[3,4],[2,3],[1,2]]

Output

cmd
[-1,0,1]

#4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def findRightInterval(self, intervals):
def binarySearch(l, r):
x, found = intervals[l - 1].end, None
while l <= r:
mid = (l + r) // 2
if intervals[mid].start >= x:
r = mid - 1
found = mid
else:
l = mid + 1
return ind[intervals[found]] if found != None else -1
root = intervals[:]
ind = {intr:i for i, intr in enumerate(root)}
intervals.sort(key = lambda x: x.start)
for i in range(len(intervals)):
root[ind[intervals[i]]] = binarySearch(i + 1, len(intervals) - 1)
return root
``````
Copy The Code &

Input

cmd
intervals = [[3,4],[2,3],[1,2]]

Output

cmd
[-1,0,1]

#5 Code Example with C# Programming

```Code - C# Programming```

``````
using System;
using System.Collections.Generic;
using System.Linq;

namespace LeetCode
{
public class _0436_FindRightInterval
{
public int[] FindRightInterval(int[][] intervals)
{
var startIndex = new SortedDictionary < int, int>();
for (int i = 0; i  <  intervals.Length; i++)
startIndex[intervals[i][0]] = i;

var results = new int[intervals.Length];
var starts = startIndex.Keys.ToArray();
for (int i = 0; i  <  intervals.Length; i++)
{
var index = Array.BinarySearch(starts, intervals[i][1]);
if (index  <  0)
index = ~index;
results[i] = index == intervals.Length ? -1 : startIndex[starts[index]];
}

return results;
}
}
}
``````
Copy The Code &

Input

cmd
intervals = [[1,4],[2,3],[3,4]]

Output

cmd
[-1,2,-1]