Queue Reconstruction by Height trong C++

Cho danh sách người đứng hàng, mỗi người là cặp (h, k): h chiều cao, k số người trước mặt có chiều cao ≥ h. Xây dựng lại hàng đợi.

Ví dụ: [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] → [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]].

Giải thuật

• Sắp xếp mảng: chiều cao tăng dần, nếu bằng nhau thì k giảm dần.
• Khởi tạo vector ans rỗng.
• Duyệt mảng đã sắp xếp từ cuối về đầu (người thấp nhất trước): chèn vào ans tại vị trí k.

Ví dụ code

#include <bits/stdc++.h>
using namespace std;

bool cmp(vector<int> a, vector<int> b) {
    if (a[0] == b[0]) return a[1] > b[1];
    return a[0] < b[0];
}

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& p) {
        sort(p.begin(), p.end(), cmp);
        vector<vector<int>> ans;
        for (int i = p.size()-1; i >= 0; i--)
            ans.insert(ans.begin() + p[i][1], p[i]);
        return ans;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{7,0},{4,4},{7,1},{5,0},{6,1},{5,2}};
    auto res = ob.reconstructQueue(v);
    for (auto& p : res) cout << "[" << p[0] << "," << p[1] << "] ";
    return 0;
}

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]]