406. Queue Reconstruction by Height

https://leetcode.com/problems/queue-reconstruction-by-height/submissions/

Problem

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Note: The number of people is less than 1,100.

Example

Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

Solution

1. $O(N^2)$ using sorting

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        auto comparator = [](const auto &a, const auto &b) {
            if (a[0] != b[0]) return a[0] < b[0];
            else return a[1] > b[1];
        };
        sort(people.begin(), people.end(), comparator);
        vector<vector<int>> queue(people.size());
        for (const auto &p: people) {
            int count = 0, i = 0;
            for (; i < queue.size(); ++i) {
                if (!queue[i].empty()) continue;
                if (p[1] == count++) break;
            }
            queue[i] = p;
        }
        return queue;
    }
};

2. $O(NlogN)$ using Binary Index Tree (BIT)

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        auto comparator = [](const auto &a, const auto &b) {
            if (a[0] != b[0]) return a[0] < b[0];
            else return a[1] > b[1];
        };
        sort(people.begin(), people.end(), comparator);
        vector<vector<int>> queue(people.size());
        vector<int> bit(people.size() + 1);
        for (int i = 1; i < people.size(); ++i) update(bit, i, 1);
        for (const auto &p: people) {
            int begin = 0, end = people.size() - 1;
            while (begin < end) {
                int mid = begin + (end - begin) / 2;
                if (query(bit, mid) < p[1]) begin = mid + 1;
                else end = mid;
            }
            queue[begin] = p;
            update(bit, begin, -1);
        }
        return queue;
    }
    inline int query(vector<int> &bit, int index) {
        index += 1;
        int sum = 0;
        while (index > 0){
            sum += bit[index];
            index -= index & -index;
        }
        return sum;
    }
    inline void update(vector<int> &bit, int index, int value) {
        index += 1;
        while (index < bit.size()){
            bit[index] += value;
            index += index & -index;
        }
    }
};

• #important

• #bit

• #sorting