```
1. Sort by height, if height is equal, sort by second item
2. Naive Algorithm:
for each item in seq:
find the new insert position and assign it to the item
3. Case analysis:
[4,4], [5,0], [5,2], [6,1], [7,0], [7,1], total 6 sorted items
that means we must fill 6 blankets. _ _ _ _ _ _
(1)[4,4] means there are 4 items before it, since no other items less than it, so it must be at the 5th pos.
(2)[5,0] means there are 0 items before it, so it must be at the first pos.
......
(6)same as before
visualize process
-----------------
_ _ _ _ _ _
_ _ _ _ [4,4] _
[5,0] _ _ _ [4,4] _
[5,0] _ [5,2] _ [4,4] _
[5,0] _ [5,2] [6,1] [4,4] _
[5,0] [7,0] [5,2] [6,1] [4,4] _
[5,0] [7,0] [5,2] [6,1] [4,4] [7,1]
4. Improved Algorithm
for each item in seq:
pos = find Kth avaliable position in newArray // K = item.second
newArray[pos] = item
used[pos] = true
Implement find_Kth() method can be done in O(n), thus total complexity is O(n^2)
5. Implement find_Kth() method in O(lgN*lgN) or O(lgN) use BIT
(1)trick #1: to convert the former "fill blanket" to "range sum"
(2)trick #2: if height[i] == height[i+1], we must delay the "convert" operation as below described
visualize process
-----------------
1 1 1 1 1 1 // first initialize all position with 1
1 1 1 1 0 1 // find [4,4] pos by calling find_Kth(4+1), pos = 5, and convert 1 to 0
1 1 1 1 0 1 // find [5,0] pos by calling find_Kth(0+1), pos = 1, do not convert 1 to 0
0 1 0 1 0 1 // find [5,2] pos by calling find_Kth(2+1), pos = 3, and convert 1 to 0
0 1 0 0 0 1 // find [6,1] pos by calling find_Kth(1+1), pos = 4, and convert 1 to 0
0 1 0 0 0 1 // find [7,0] pos by calling find_Kth(0+1), pos = 2, do not convert 1 to 0
0 0 0 0 0 0 // find [7,1] pos by calling find_Kth(1+1), pos = 6, convert 1 to 0
```

Dirty Code Below......

Hope someone can post a nice and clean code.....

```
class Solution {
public:
typedef pair<int,int> Node;
vector<int> c;
int n;
vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
int len = people.size();
vector<Node> ans(len);
vector<int> tmp(len+2,0);
c = tmp;
n = len;
//initialize
for(int i = 1; i <= n; i++)update(i,1);
sort(people.begin(), people.end());
int pre = -1;
vector<int> preNum;
for(int i = 0; i < len; i++)
{
//amotized O(1) operation
if(people[i].first != pre)
{
for(int j = 0; j < preNum.size(); j++)update(preNum[j],-1);
preNum.clear();
}
int num = findKth(people[i].second+1);
ans[num-1] = people[i];
preNum.push_back(num);
pre = people[i].first;
}
return ans;
}
//Binary Index Tree update
void update(int idx, int val)
{
while(idx <= n)
{
c[idx] += val;
idx += idx & -idx;
}
}
//Binary Index Tree getSum [1, idx]
int getsum(int idx)
{
int sum = 0;
while(idx > 0)
{
sum += c[idx];
idx -= idx & -idx;
}
return sum;
}
//find-Kth position, Here I use Binary-search, So complexity is O(lgN*lgN)
int findKth(int k)
{
int l = 1, r = n, mid;
while(l <= r)
{
mid = (l + r) >> 1;
if(getsum(mid) >= k)r = mid - 1;
else l = mid + 1;
}
return l;
}
bool static cmp(Node a, Node b)
{
if(a.first == b.first)return a.second < b.second;
return a.first < b.first;
}
};
//Another O(lgN) find_Kth implementaiton
/*
int find_kth(int k)
{
int cnt = 0, ans = 0;
for(int i = 20; i >=0; i--)
{
ans += 1 << i;
if(ans >= n || cnt + c[ans] >= k)ans -= 1 << i;
else cnt += c[ans];
}
return ans + 1;
}
*/
```