Alternative solution (sort twice)


  • 0
    H

    Sort the intervals twice:
    byStart -> sort by start
    byEnd -> sort by end
    end for each interval in byEnd we check byStart.
    If start >= end then we record the index.
    else we advance the byStart index.

    class Solution {
        public int[] findRightInterval(Interval[] intervals) {        
            Map<Integer, Integer> startToIndex = new HashMap<>();
            for (int i=0; i<intervals.length; i++) {
                startToIndex.put(intervals[i].start, i);
            }
            Interval[] byStart = Arrays.copyOf(intervals, intervals.length);
            Arrays.sort(byStart, (i1, i2) -> i1.start - i2.start);
            Interval[] byEnd = Arrays.copyOf(intervals, intervals.length);
            Arrays.sort(byEnd, (i1, i2) -> i1.end - i2.end);
            int[] result = new int[intervals.length];
            int index = 0;
            for (int i=0; i<byEnd.length; i++) {
                while (index < byStart.length && byStart[index].start < byEnd[i].end) {
                    index++;
                }
                if (index < byStart.length) {
                    result[startToIndex.get(byEnd[i].start)] = startToIndex.get(byStart[index].start);
                } else {
                    result[startToIndex.get(byEnd[i].start)] = -1;
                }
            }
            return result;
        }
    }
    

Log in to reply
 

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