Sharing my binary search version, beat 67%


  • 0

    Used a hashmap for mapping index

    public int[] findRightInterval(Interval[] intervals) {
            int[] result = new int[intervals.length];
            HashMap<Integer, Integer> startMap = new HashMap();
            for (int i = 0; i < intervals.length; i++) startMap.put(intervals[i].start, i);
            Arrays.sort(intervals, new Comparator<Interval>() {
                @Override
                public int compare(Interval i1, Interval i2) {
                    return Integer.compare(i1.start, i2.start);
                }
            });
    
            for (Interval interval: intervals) {
                int start = 0, end = intervals.length - 1, index = -1;
                boolean found = false;
                while (start + 1 < end) {
                    int mid = (start + end) / 2;
                    if (intervals[mid].start < interval.end) {
                        start = mid;
                    } else if (intervals[mid].start == interval.end) {
                        index = startMap.get(intervals[mid].start);
                        found = true;
                        break;
                    } else {
                        end = mid;
                    }
                }
                if (found) {
                     result[startMap.get(interval.start)] = index;
                     continue;
                }
                if (intervals[end].start >= interval.end) index = startMap.get(intervals[end].start);
                if (intervals[start].start >= interval.end) index = startMap.get(intervals[start].start);
                result[startMap.get(interval.start)] = index;
            }
            return result;
        }
    

Log in to reply
 

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