My 22ms Java Solution, O(nlogn), simple and easy


  • 1
    public class Solution {
        class myNode{
            int start;
            int idx;
            public myNode(int start, int idx){
                this.start = start; this.idx = idx;
            }
        }
        public int[] findRightInterval(Interval[] intervals) {
            int[] ret = new int[intervals.length];
            if(intervals.length<1) return ret;
            myNode[] ends = new myNode[intervals.length];
            for(int i=0;i<intervals.length;i++) ends[i] = new myNode(intervals[i].start, i);
            Arrays.sort(ends, new Comparator<myNode>(){
                public int compare(myNode A, myNode B){
                    if(A.start!=B.start) return A.start-B.start;
                    else return A.idx-B.idx;
                }
            });
            for(int i=0;i<intervals.length;i++) ret[i] = search(intervals, ret, ends, i);
            return ret;
        }
        public int search(Interval[] intervals, int[] ret, myNode[] ends, int start){
            int lo = 0, hi = ret.length-1;
            while(lo<hi){
                int mid = lo + (hi-lo)/2;
                if(ends[mid].start>=intervals[start].end && ends[mid].idx!=start) hi = mid;
                else lo = mid +1;
            }
            return ends[lo].start>=intervals[start].end && ends[lo].idx != start?ends[lo].idx:-1;
        }
    }
    

  • 0

    If I understand correctly, you put start value and index into a new array, sort them based on start value. And according to every end value, use binary search to search inside the new array for the least value that greater or equal to the end value.
    Could you explain a little bit about the search method return statement?
    return ends[lo].start>=intervals[start].end && ends[lo].idx != start?ends[lo].idx:-1;

    what's the meaning to have ends[lo].idx != start?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.