java nlog(n) hashmap and binary search solution,very easy to understand


  • 0
    W
    /**
     * 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 class MyComparator implements Comparator<Interval> {
            @Override
            public int compare(Interval i1, Interval i2) {
                return i1.start < i2.start ? -1 : 1;
            }
        }
        public int[] findRightInterval(Interval[] intervals) {
            if (intervals == null || intervals.length == 0) {
                return new int[]{};
            }
            Map<Interval, Integer> map = new HashMap<>();
            for (int i = 0; i < intervals.length; i++) {
                map.put(intervals[i], i);
            }
            int[] result = new int[intervals.length];
            Arrays.sort(intervals, new MyComparator());
            //System.out.println(intervals);
            loop:
            for (int i = 0; i < intervals.length; i++) {
                int target = intervals[i].end;
                int left = i;
                int right = intervals.length - 1;
                while (left + 1 < right) {
                    int mid = left + (right - left) / 2;
                    if (intervals[mid].start == target) {
                        result[map.get(intervals[i])] = map.get(intervals[mid]);
                        continue loop;
                    } else if (intervals[mid].start > target) {
                        right = mid;
                    } else {
                        left = mid + 1;
                    }
                }
                if (intervals[left].start >= target) {
                    result[map.get(intervals[i])] = map.get(intervals[left]);
                } else if (intervals[right].start >= target) {
                    result[map.get(intervals[i])] = map.get(intervals[right]);
                } else {
                    result[map.get(intervals[i])] = -1;
                }
            }
            return result;
        }
    }
    

Log in to reply
 

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