C++-এ রাশিয়ান ডল এনভেলপস (Russian Doll Envelopes)

রাশিয়ান ডল এনভেলপস সমস্যা

কিছু এনভেলপ (লিফাফা) দেওয়া আছে, প্রতিটির উচ্চতা এবং প্রস্থ। একটি এনভেলপ অন্যটির মধ্যে রাখা যাবে যদি এর উভয় মাত্রা অন্যটির চেয়ে ছোট হয়। সর্বোচ্চ কতটি এনভেলপ একে অপরের মধ্যে রাখা যাবে?

উদাহরণ: [[5,5], [6,4], [6,8], [2,3]] → উত্তর ৩ ([2,3] → [5,5] → [6,8])

সমাধানের পদ্ধতি (LIS - লองেস্ট ইনক্রিজিং সাবসিকোয়েন্স)

• এনভেলপগুলো উচ্চতা বর্ধমান, প্রস্থ হ্রাসমান ক্রমে সর্ট করুন (একই উচ্চতা হলে প্রস্থ বড়টি আগে)
• তারপর প্রস্থের ওপর LIS (Longest Increasing Subsequence) খুঁজুন
• বাইনারি সার্চ ব্যবহার করে O(n log n) সময়ে LIS গণনা করুন

C++ কোড উদাহরণ

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

class Solution {
public:
    static bool cmp(vector<int> a, vector<int> b) {
        if(a[0] == b[0]) return a[1] > b[1];
        return a[0] < b[0];
    }
    
    int maxEnvelopes(vector<vector<int>>& v) {
        sort(v.begin(), v.end(), cmp);
        if(v.size() == 0) return 0;
        vector<int> ret;
        for(int i = 0; i < v.size(); i++) {
            int x = v[i][1];
            int low = 0, high = (int)ret.size() - 1, curr = 0;
            while(low <= high) {
                int mid = low + (high - low) / 2;
                if(ret[mid] < x) {
                    curr = mid + 1;
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
            if(curr < 0) continue;
            if(curr >= (int)ret.size()) ret.push_back(x);
            else ret[curr] = x;
        }
        return ret.size();
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{5,5}, {6,4}, {6,8}, {2,3}};
    cout << (ob.maxEnvelopes(v));
    return 0;
}

ইনপুট

{{5,5}, {6,4}, {6,8}, {2,3}}

আউটপুট

3