[Java] Abstract + Sort


  • 1
    K

    Same as other interval problem,

    1. do one level abstraction,
    2. sort them based on the index val, the start/falling type.
    3. Scan through the sorted list. Here we use a stack as temporary storage.

    TimeComplexity:
    O(nlogn) Sorting + O(n)(Every node goes into stack and comes out of it at most once)

        public class Node implements Comparable<Node> {
            int idx; // which interval it belongs too
            int val;
            int flag; // 0 equals end, 1 equals start;
            public Node (int idx, int val, int flag) {
                this.idx = idx;
                this.val = val;
                this.flag = flag;
            }
            @Override
            public int compareTo(Node that){
                if(this.val != that.val){
                    return this.val - that.val;
                } else {
                    return this.flag - that.flag;
                }
            }
            
        }
        public int[] findRightInterval(Interval[] intervals) {
            // One solution is to do one level abstraction
            // Store the point along with its start,end, idx.
            // Sort all the points.
            if(intervals == null || intervals.length == 0) return null;
            int len = intervals.length;
            int[] res = new int[len];
            Arrays.fill(res, -1);
            
            //Iterate these the sorted point, if it's start point, pop whatever inside of stk and mark
            // their next as current start point's idx
            List<Node> nodes = new ArrayList<>();
            
            int cnt = 0;
            for(Interval itv : intervals) {
                Node node1 = new Node(cnt, itv.start, 1);
                Node node2 = new Node(cnt, itv.end, 0);
                nodes.add(node1);
                nodes.add(node2);
                cnt++;
            }
            
            /*2nlog2n Time complexity*/
            Collections.sort(nodes);
           
            Stack<Integer> stk = new Stack<>();
            for(Node node : nodes) {
                if(node.flag == 0) {
                    stk.push(node.idx);
                } else {
                    int start_idx = node.idx;
                    while(!stk.isEmpty()) {
                        int end_idx = stk.pop();
                        res[end_idx] = start_idx;
                    }
                }
            }
            
            return res;
        }
    

Log in to reply
 

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