Java O(nlogn) tow pointers


  • 0
    H
    public class Solution {
        class Cell{
            int start;
            int end;
            int index;
            Cell(int s,int e,int i){start=s;end=e;index=i;}
        }
        public int[] findRightInterval(Interval[] intervals) {
            int length=intervals.length;
            int[] res=new int[length];
            Cell[] cells=new Cell[length];
            if(length==0)
                return res;
            for(int i=0;i<length;i++){
                cells[i]=new Cell(intervals[i].start,intervals[i].end,i);
            }
            Cell[] cells2=new Cell[length];
            System.arraycopy(cells,0,cells2,0,length);
            Arrays.sort(cells,new Comparator<Cell>(){
                public int compare(Cell i1,Cell i2){
                    if(i1.end==i2.end){
                        return i1.start-i2.start;
                    }
                    else{
                        return i1.end-i2.end;
                    }
                }
            });
            Arrays.sort(cells2,new Comparator<Cell>(){
                public int compare(Cell i1,Cell i2){
                    return i1.start-i2.start;
                }
            });
            for(int i=0,j=0;i<length;i++){
                int end=cells[i].end;
                while(j<length&&cells[i].end>cells2[j].start){
                    j++;
                }
                if(j!=length){
                    res[cells[i].index]=cells2[j].index;
                }
                else{
                    res[cells[i].index]=-1;
                }
            }
            return res;
        }
    

Log in to reply
 

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