Java segment tree using lazy propagation solution with explanation. (42ms 83%)


  • 1
    S

    Step1: Sort all building start points and end points, these would form the two ends of intervals. If our input is [3, 7, 8], [3, 8, 7], [3, 9, 6]. Then we sort [3, 7, 3, 8, 3, 9] to get [3,3,3,7,8,9], key points must come from these points.

    Step2: Since there are probably duplicate points in step 1. Create a mapping from the unique points to index [0,1,2,3,...]. In our example, 3 -> 0, 7 -> 1, 8-> 2, 9-> 3. The intervals we use in our segment tree to represent the maximum interval heights are left closed, right open. So the value of the first leaf node of our segment tree, denotes the max height of interval [3, 7). The value of second denotes the max height of interval [7, 8), etc.

    Step3: Create an empty segment tree with n leaf nodes, where n is the size of unique points in step1. So we now have a data structure to represent the max heights of intervals: [p0, p1) , [p1, ...p2) .... [p_{n-2}, p_{n-1}), [p_{n-1}, \infty). Then for each building, update it's corresponding intervals using it's height.

    Note we are doing range update here, so lazy propagation is used to guarantee O(log n) operation. Also note we only care about the maximum height, so only update segment tree or lazy values if they are smaller.

    Step4: Query each simple interval (or leaf interval), if the max height on that simple interval is different from the max height of previous interval, it must be a key point. Add it to the result.

    Note each simple interval correspond to one leaf node. We only need query on single index and update on range from our segment tree.

    Complexity: Time O(nlogn) Space O(nlogn).

    public class Solution {
        public List<int[]> getSkyline(int[][] buildings) {
            List<Integer> locations = new ArrayList<Integer>();
            for(int[] building: buildings){
                locations.add(building[0]);
                locations.add(building[1]);
            }
            Collections.sort(locations);
            
            Map<Integer, Integer> loc2Idx = new HashMap<Integer, Integer>();
            int idx = 0;
            for(int i: locations)
                if(!loc2Idx.containsKey(i))     loc2Idx.put(i, idx++);
            
            SegmentTree st = new SegmentTree(idx+1);
            for(int[] building: buildings)          // use interval [i, j)
                st.updateRange(loc2Idx.get(building[0]), loc2Idx.get(building[1])-1, building[2]);
            
            List<int[]> res = new ArrayList<int[]>();
            int prevHeight = 0;
            for(int i = 0; i < locations.size(); i++){
                int curHeight = st.getMax(loc2Idx.get(locations.get(i)));
                if(curHeight != prevHeight)     res.add(new int[]{locations.get(i), curHeight});
                prevHeight = curHeight;
            }
            return res;
        }
    }
    class SegmentTree{
        private int[] st;
        private int[] lazy;     // lazy[i] == 0: up to date; lazy[i] > 0: potential update note we use the fact that min>=0 always
        private int N;
        public SegmentTree(int N){
            this.N = N;
            if(N == 0)  return;
            int height = (int) Math.ceil( Math.log(N) / Math.log(2) );
            int maxSize = 2 * (int) Math.pow(2, height) - 1;
            this.st = new int[maxSize];
            this.lazy = new int[maxSize];
        }
        public void updateRange(int i, int j, int val){
            if(N == 0)  return;
            updateRangeUtil(0, N-1, i, j, val, 0);
        }
        private void updateRangeUtil(int ss, int se, int qs, int qe, int val, int si){
            if(lazy[si] > 0){
                if(st[si] < lazy[si])       st[si] = lazy[si];
                if(ss != se){               // not leaf
                    if(lazy[2*si + 1] < lazy[si])	lazy[2*si + 1] = lazy[si];
                    if(lazy[2*si + 2] < lazy[si])	lazy[2*si + 2] = lazy[si];
                }
                lazy[si] = 0;
            }
            if(qe < ss || se < qs)      return;         // no overlap
            if(qs <= ss && se <= qe){                   // total overlap
                if(st[si] < val)   st[si] = val;
                if(ss != se){
                	if(lazy[2*si + 1] < val)	lazy[2*si + 1] = val;
                	if(lazy[2*si + 2] < val)	lazy[2*si + 2] = val;
                }            
            }else if(ss < se){              // not leaf
                int mid = getMid(ss, se);
                updateRangeUtil(ss, mid, qs, qe, val, 2*si + 1);
                updateRangeUtil(mid+1, se, qs, qe, val, 2*si + 2);
                st[si] = st[2*si+1] > st[2*si+2] ? st[2*si+1] : st[2*si+2];
            }
        }
        public int getMax(int i){
            if(N == 0)  return 0;
            return getMaxUtil(0, N-1, i, 0);
        }
        private int getMaxUtil(int ss, int se, int idx, int si){
        	if(lazy[si] > 0){
        		if(st[si] < lazy[si])	st[si] = lazy[si];
        		if(ss != se){
        			if(lazy[2*si + 1] < lazy[si])	lazy[2*si + 1] = lazy[si];
        			if(lazy[2*si + 2] < lazy[si])	lazy[2*si + 2] = lazy[si];
        		}
        		lazy[si] = 0;
        	}        
            if(ss == se)            return st[si];          // leaf
            else{                                           // not leaf
                int mid = getMid(ss, se);
                if(idx <= mid)      return getMaxUtil(ss, mid, idx, 2*si+1);
                else                return getMaxUtil(mid+1, se, idx, 2*si+2);
            }
        }
        private int getMid(int ss, int se){
            return ss + (se - ss)/2;
        }
    }

Log in to reply
 

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