7ms Java solution using only arrays


  • 0
    M
    /**
     * Definition for an interval.
     * public class Interval {
     *     int start;
     *     int end;
     *     Interval() { start = 0; end = 0; }
     *     Interval(int s, int e) { start = s; end = e; }
     * }
     */
    public class Solution {
        public int[] findRightInterval(Interval[] intervals) {
            int res[]=new int[intervals.length];
            int max=Integer.MIN_VALUE;
            int min=Integer.MAX_VALUE;
            for(int i=0;i<intervals.length;i++){
                max=Math.max(max,intervals[i].start);
                min=Math.min(min,intervals[i].start);
            }
            int index[]=new int[(max-min)+1];
            for(int i=0;i<index.length;i++){
                index[i]=-1;
            }
            for(int i=0;i<intervals.length;i++){
                index[intervals[i].start-min]=i;
            } 
            for(int i=0;i<intervals.length;i++){
                int cur=intervals[i].end-min;
                if(cur>max-min) {res[i]=-1;continue;}
                int j=cur;
                while(index[j]==-1&&j<max-min){
                    j++;
                }
                res[i]=index[j];
            }
            return res;
        }
    }
    

Log in to reply
 

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