```
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;
}
}
```