Leetcode Find Right Interval problem solution

by

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.

Leetcode Find Right Interval problem solution

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;
}