Java segment tree and binary indexed tree solution.


  • 0
    S
    public class Solution {
        public int[][] reconstructQueue(int[][] people) {
            Arrays.sort(people, new Comparator<int[]>(){
    			public int compare(int[] p1, int[] p2){
    			    if(p2[0] != p1[0]){
    				    return p1[0] - p2[0];
    			    }else{
    			        return p2[1] - p1[1];
    			    }
    			}
    		});
    		
    		SegTree seg = new SegTree(people.length);
    
    		int[][] res = new int[people.length][2];
    		for(int[] person: people){
    			int idx = seg.getAndRemoveKth(person[1] + 1) - 1;
    			res[idx] = person;
    		}
    		return res;
        }
    }
    
    class SegTree{
    		int[] st;
    		int[] arr;
    		
    		public SegTree(int N){
    			arr = new int[N+1];	// 1: available  0: occupied
    			Arrays.fill(arr, 1);
    			arr[0] = 0;
    
    			int b = 1;
    			while(b < N+1){
    				b = b << 1;				
    			}
    			st = new int[2*b-1];
    			constructUtil(0, N, 0);
    		}
    		
    		private int constructUtil(int arrLo, int arrHi, int stIdx){
    			if(arrLo == arrHi){
    				st[stIdx] = arr[arrLo];
    			}else{
    				int mid = arrLo + (arrHi - arrLo) / 2;
    				st[stIdx] = constructUtil(arrLo, mid, 2 * stIdx + 1) + constructUtil(mid + 1, arrHi, 2 * stIdx + 2);
    			}
    			return st[stIdx];
    		}
    		
    		public int getAndRemoveKth(int k){
    			int res = getKthUtil(0, arr.length - 1, k, 0);
    			arr[res] = 0;
    			removeKthUtil(0, arr.length - 1, res, 0);
    			return res;
    		}		
    
    		private int getKthUtil(int arrLo, int arrHi, int k, int stIdx){
    			if(st[stIdx] == k && arr[arrHi] == 1){
    				return arrHi;
    			}
    			int mid = arrLo + (arrHi - arrLo) / 2;
    			if(st[2 * stIdx + 1] >= k){
    				return getKthUtil(arrLo, mid, k, 2 * stIdx + 1);
    			}else{
    				return getKthUtil(mid + 1, arrHi, k - st[2 * stIdx + 1], 2 * stIdx + 2);
    			}
    		}
    		
    		private void removeKthUtil(int arrLo, int arrHi, int K, int stIdx) {
    			if(K < arrLo || arrHi < K){
    				return;
    			}
    			st[stIdx]--;
    			if(arrLo < arrHi){
    				int mid = arrLo + (arrHi - arrLo) / 2;
    				removeKthUtil(arrLo, mid, K, 2 * stIdx + 1);
    				removeKthUtil(mid + 1, arrHi, K, 2 * stIdx + 2);
    			}			
    		}		
    }
    
    public class Solution {
        public int[][] reconstructQueue(int[][] people) {
            Arrays.sort(people, new Comparator<int[]>(){
    			public int compare(int[] p1, int[] p2){
    			    if(p2[0] != p1[0]){
    				    return p1[0] - p2[0];
    			    }else{
    			        return p2[1] - p1[1];
    			    }
    			}
    		});
    		
    		BITRQ bit = new BITRQ(people.length);
    
    		int[][] res = new int[people.length][2];
    		for(int[] person: people){
    			int idx = bit.getAndRemoveKth(person[1] + 1) - 1;
    			res[idx] = person;
    		}
    		return res;
        }
    }
    class BITRQ{
    		private int[] bit;	
    		public BITRQ(int N){		// empty: 1, occupied: 0
    			bit = new int[N+1];
    			for(int i = 0; i < N; i++){
    				set(i, 1);
    			}
    		}
    		
    		public int getAndRemoveKth(int rank){
    			int ans = getRank(rank);
    			set(ans - 1, -1);
    			return ans;
    		}
    		
    		private void set(int idx, int val){
    			for(idx++; idx < bit.length; idx += (idx & -idx)){
    				bit[idx] += val;				
    			}
    		}
    		
    		private int getRank(int rank){
    			int N = bit.length - 1, mask = 1;
    			while(mask < N){
    				mask <<= 1;
    			}
    			mask >>= 1;
    			int startIdx = 0;
    			while(mask > 0){
    				if(startIdx + mask < bit.length && rank > bit[startIdx + mask]){
    					rank -= bit[startIdx + mask];
    					startIdx += mask;
    				}
    				mask >>= 1;
    			}
    			return startIdx + 1;
    		}
    	}
    

Log in to reply
 

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