# Leetcode Find Right Interval problem solution

In this Leetcode Find Right Interval problem solution 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.

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.

## Problem solution in Python.

```def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
if not intervals:
return []

res = [-1] * len(intervals)
start_ascending = sorted([(start, idx) for idx, (start, end) in enumerate(intervals)])
end_ascending = sorted([(end, idx) for idx, (start, end) in enumerate(intervals)])
idx1, idx2 = 0, 0
while True:
while idx1 < len(start_ascending) and start_ascending[idx1][0] < end_ascending[idx2][0]:
idx1 += 1
if idx1 == len(start_ascending):
break

while idx2 < len(end_ascending) and end_ascending[idx2][0] <= start_ascending[idx1][0]:
res[end_ascending[idx2][1]] = start_ascending[idx1][1]
idx2 += 1
if idx2 == len(start_ascending):
break
return res
```

## Problem solution in Java.

```class Solution {
public int[] findRightInterval(int[][] intervals) {
TreeMap<Integer, Integer> map = new TreeMap<>();
int[] res = new int[intervals.length];
for(int i = 0; i < intervals.length; i++){
map.put(intervals[i][0], i);
}

for(int i = 0; i < intervals.length; i++){
res[i] = map.ceilingKey(intervals[i][1]) == null ? -1 : map.get(map.ceilingKey(intervals[i][1]));
}
return res;
}
}
```

## Problem solution in C++.

```vector<int> findRightInterval(vector<vector<int>>& intervals) {
map<int, int> dict;
for(int i=0; i<intervals.size(); i++) dict[intervals[i][0]]=i;
vector<int> result;
for(auto interval : intervals) {
int end=interval[1];
auto it=dict.lower_bound(end);
if(it==dict.end())
result.push_back(-1);
else
result.push_back(it->second);
}
return result;
}```

## Problem solution in C.

```int cmp(void* a, void* b){
return (*(int**)a)[0]-(*(int**)b)[0];
}
int cmp1(void* a, void* b){
return (*(int**)a)[1]-(*(int**)b)[1];
}
int* findRightInterval(struct Interval* intervals, int intervalsSize, int* returnSize) {
int* ret=(int*)calloc(intervalsSize,sizeof(int));
*returnSize=intervalsSize;
struct Interval* q=intervals;
int** array=(int**)malloc(intervalsSize*sizeof(int*));
int** array1=(int**)malloc(intervalsSize*sizeof(int*));
for(int i=0;i<intervalsSize;i++){
array[i]=(int*)calloc(3,sizeof(int));
array[i][0]=q->start;
array[i][1]=q->end;
array[i][2]=i;
array1[i]=(int*)calloc(3,sizeof(int));
array1[i][0]=q->start;
array1[i][1]=q->end;
array1[i][2]=i;
q++;
}
qsort(array,intervalsSize,sizeof(array[0]),cmp);
qsort(array1,intervalsSize,sizeof(array1[0]),cmp1);
int i=0;
int j=0;
for(;i<intervalsSize;i++){
for(;j<intervalsSize;j++){
if(array1[i][1]<=array[j][0]){
ret[array1[i][2]]=array[j][2];
break;
}
}
if(j==intervalsSize){
ret[array1[i][2]]=-1;
}
}
return ret;
}
```