JAVA O(nlogn) HashMap+Binary Search (44ms)


  • 0
    W
    public int[] findRightInterval(Interval[] intervals) {
        if(intervals == null || intervals.length == 0) return new int[0];
        int[] res = new int[intervals.length];
        Arrays.fill(res, -1);
        
        //put interval and the index together in map
        Map<Interval, Integer> map = new HashMap<>();
        for(int i = 0; i < intervals.length; i++) {
            map.put(intervals[i], i);
        }
        
        //sort intervals accordig to start time
        Arrays.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval i1, Interval i2) {
                return i1.start - i2.start;
            }
        });       
        
        
        //after sort, use binary seach to find the minimum right interval, don't update result if right interval does not exist
        for(int i = 0; i < intervals.length; i++) {
            int start = i + 1, end = intervals.length - 1;
            while(start < end) {
                int mid = (start + end) / 2;
                if(intervals[i].end > intervals[mid].start) {
                    start = mid + 1;
                } else {
                    end = mid;
                }
            }
            
            if(intervals[i].end <= intervals[end].start)
                res[map.get(intervals[i])] = map.get(intervals[end]);
        }
        
        return res;
    }

Log in to reply
 

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