Java scan through the points in one pass O(nlogn)


  • 0

    The idea is whenever you see a start point you assign its interval as the miminum right interval to those unmatched previous intervals and remove those intervals from the waiting list. Whenever you see a end point, add the corresponding interval to the waiting list to be matched. One caveat is for points with the same location, end point should appear earlier than any start point so we can add the interval first and then find a right interval for it.

    public static class Point implements Comparable<Point> {
            int val, interval;
            boolean left;
            public Point(int v, int itvl, boolean l) {
                val = v;
                interval = itvl;
                left = l;
            }
            public int compareTo(Point that) {
                if (this.val < that.val) return -1;
                else if (this.val > that.val) return 1;
                else if (this.left) return 1;
                else if (that.left) return -1;
                else return 0;
            }
    
        }
        public static int[] findRightInterval(Interval[] intervals) {
            int n = intervals.length;
            int[] result = new int[n];
            for (int i = 0; i < n; i++) result[i] = -1;
            Point[] points = new Point[2*n];
            int k = 0;
            for (int i = 0; i < intervals.length; i++) {
                points[k++] = new Point(intervals[i].start, i, true);
                points[k++] = new Point(intervals[i].end, i, false);
            }
            Arrays.sort(points);
            k = 0;
            HashSet<Integer> set = new HashSet<>();
            while (k < 2*n) {
                if (points[k].left) {
                    for (int i : set) result[i] = points[k].interval;
                    set.clear();
                    k++;
                } else set.add(points[k++].interval);
            }
            return result;
        }
    

Log in to reply
 

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