Two O(N*lgN) solutions


  • 0
    I
        public int[] findRightInterval(Interval[] intervals) {
         
            final int[] ans = new int[intervals.length];
            Arrays.fill(ans, 0, ans.length, -1);
         
            if(intervals.length <= 1) return ans;
            
            final TreeMap<Integer, Integer> offer = new TreeMap<>();
    
            for(int i=0; i<intervals.length; i++) {
                final Interval interval = intervals[i];
                
                if(!offer.containsKey(interval.start)) {
                    offer.put(interval.start, i);
                }
            }
    
            for(int i=0; i<intervals.length; i++) {
                final Interval interval = intervals[i];
                
                final Integer ceiling = offer.ceilingKey(interval.end);
                
                if(ceiling != null) {
                    ans[i] = offer.get(ceiling);
                }
            }
            
            return ans;
        }
    
        public int[] findRightInterval(Interval[] intervals) {
            final int[] ans = new int[intervals.length];
            Arrays.fill(ans, 0, ans.length, -1);
         
            if(intervals.length <= 1) return ans;
            
            final int[] ends = new int[intervals.length];
            for(int i=0; i<ends.length; i++) {
                ends[i] = intervals[i].end;
                intervals[i].end = i;
            }
            
            Arrays.sort(intervals, (i1, i2) -> i1.start - i2.start);
            
            final Interval interval = new Interval(0, Integer.MAX_VALUE);
            
            for(int i=0; i<ends.length; i++) {
                interval.start = ends[i];
                
                int index = Arrays.binarySearch(intervals, interval, (i1, i2) -> i1.start - i2.start);
                
                if(index < 0) {
                    index = -(index + 1);
                }
                
                if(index < ends.length) {
                    ans[i] = intervals[index].end;
                }
            }
            
            return ans;
        }
     
    
    

Log in to reply
 

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