C++-এ Queue Reconstruction by Height

এই সমস্যায় লোকজনের একটি র‍্যান্ডম কিউ দেওয়া থাকলে, প্রতিটি লোককে (h, k) পেয়ার দিয়ে বর্ণনা করা হয়েছে: h = উচ্চতা, k = তার সামনে কতজন লোক আছে যাদের উচ্চতা h-এর চেয়ে বড় বা সমান। আসল কিউ রিকনস্ট্রাক্ট করতে হবে।

উদাহরণ: [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] -> আউটপুট [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]।

সমাধানের পদ্ধতি (Greedy + Insertion)

• অ্যারেকে সর্ট করুন: উচ্চতা ডিসেন্ডিং, আর সমান উচ্চতা হলে k অ্যাসেন্ডিং।
• খালি একটি লিস্ট ans নিয়ে শুরু করুন।
• সর্টেড অ্যারেতে থেকে প্রতিটি পেয়ার p এর জন্য, ans-এ ইন্ডেক্স p[1]-এ ইন্সার্ট করুন। কারণ সেটির চেয়ে লम्बা লোকরা ইতিমধ্যে বসানো আছে, তাই তার সামনে ঠিক k জন থাকবে।

উদাহরণ (C++)

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

void printVec(vector<vector<int>> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) {
        cout << "[" << v[i][0] << ", " << v[i][1] << "]" << (i+1==v.size()?"":", ");
    }
    cout << "]" << endl;
}

bool cmp(const vector<int>& a, const vector<int>& b) {
    if (a[0] == b[0]) return a[1] < b[1]; // height same -> k ascending
    return a[0] > b[0]; // height descending
}

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

int main() {
    Solution ob;
    vector<vector<int>> v = {{7,0}, {4,4}, {7,1}, {5,0}, {6,1}, {5,2}};
    printVec(ob.reconstructQueue(v));
    return 0;
}

ইনপুট

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

আউটপুট

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