Java Sweep-Line Solution O(nlogn)


  • 4
    1. wrapper class: Point
      1. value
      2. flag: 1 indicates start, 2 indicates end
      3. index: original pos in intervals array
      4. Comparable: sort by value ascending, end in front of start if they have same value.
    1. Iterate intervals array and fill a points list, then sort it

    2. Iterate points list, since the sequence will be "order by position, and end will come before start".

      1. whenever meet a end point, keep a list(prevIdxs) before next start, save original index of curr interval to the list.
      2. whenever meet a start point, this start point is the right interval to the intervals in the list (prevIdxs). Take out each index in it and update to result.
    class Point implements Comparable<Point>{
        int val;
        int flag; //1 start, 0 end
        int index;
        public Point(int val, int flag, int index) {
            this.val = val;
            this.flag = flag;
            this.index = index;
        }
        public int compareTo(Point o) {
            if (this.val == o.val) return this.flag - o.flag; //end in front of start
            return this.val - o.val;
        }
    }
    public int[] findRightInterval(Interval[] intervals) {
        if (intervals == null || intervals.length == 0) return new int[]{};
        
        int[] res = new int[intervals.length];
        Arrays.fill(res, -1);
        
        List<Point> points = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            points.add(new Point(intervals[i].start, 1, i));
            points.add(new Point(intervals[i].end, 0, i));
        }
        
        Collections.sort(points);
        
        List<Integer> prevIdxs = new ArrayList<>();
        
        for (Point point: points) {
            if (point.flag == 1) {
                    for (Integer prevIdx: prevIdxs) {
                       res[prevIdx] = point.index; 
                    }
                    prevIdxs = new ArrayList<>();
            } else {
                prevIdxs.add(point.index);
            }
        }
        
        return res;
    }

  • 0
    S

    Looks great to me! But it looks like you initialize and alter the variable "prevEnd" without ever using it. Maybe it's left over from a previous idea?


  • 0

    @scheung Thank you, you are right. I modified my code to delete unused lines.


  • 2
    C

    Nice solution. It seems a new idea besides TreeMap or Binary Search. But I think prevIdxs.clear() will be better than new ArrayList<>().


  • 0
    L

    The key thing is Colletions.sort(point) instead of Collections.sort(intervals)


Log in to reply
 

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