Java nlogn based on Meeting Room solution


  • 0
    F
    // like meeting room
        public int[] findRightInterval(Interval[] intervals) {
            if (intervals.length == 0) return new int[0];
            int n = intervals.length;
            int[][] start = new int[n][2];
            int[][] end = new int[n][2];
            int[] res = new int[n];
            for (int i = 0; i < n; i++) {
                start[i] = new int[]{intervals[i].start, i};
                end[i] = new int[]{intervals[i].end, i};
            }
            Arrays.sort(start,(s1, s2)->{
                return s1[0]-s2[0];
            });
            Arrays.sort(end, (e1, e2)->{
                return e1[0]-e2[0];
            });
            int j = n;
            for (int i = n-1; i >= 0; i--) {
                while (start[j-1][0] >= end[i][0]) j--;
                if (j != n) res[end[i][1]] = start[j][1];
                else res[end[i][1]] = -1;
            }
            return res;
        }

Log in to reply
 

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