Clean Java O(n logn) solution: hashmap + binary search


  • 0
    Y
        public int[] findRightInterval(Interval[] intervals) {
            int[] result = new int[intervals.length];
            // map records the index for each start point
            HashMap<Integer, Integer> map = new HashMap();
            for(int i = 0; i < intervals.length; i ++) {
                map.put(intervals[i].start, i);
            }
            
            //sort according to start point
            Arrays.sort(intervals, (a, b)->(a.start-b.start));
            
            //binary search to insert current end point to larger sorted start points
            for(int i = 0; i < intervals.length; i ++) {
                int target = intervals[i].end;
                int left = i + 1, right = intervals.length;
                while(left < right) {
                    int mid = (right-left)/2 + left;
                    if(intervals[mid].start < target) left = mid + 1;
                    else right = mid;
                }
                result[map.get(intervals[i].start)] = (right == intervals.length) ? -1 : map.get(intervals[right].start);
            }
            return result;
        }
    

Log in to reply
 

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