C++-এ রেক্ট্যাঙ্গেল একে অপরের ভেতরে রাখার পর বাকি থাকা মিনিমাম সংখ্যা

সমস্যা

Nটি রেক্ট্যাঙ্গেলের প্রস্থ ও উচ্চতা দেওয়া। একটিকে অন্য একটির ভেতরে রাখা যায় যদি উভয় প্রস্থ ও উচ্চতা ছোট হয়। সর্বোচ্চ নেস্টিং করার পর বাকি থাকা রেক্ট্যাঙ্গেলের ন্যূনতম সংখ্যা বের করুন।

অ্যালগরিদম: লองেস্ট ইনক্রিজিং সাবসিকোয়েন্স (LIS) ভ্যারিয়েন্ট

1. রেক্ট্যাঙ্গেলগুলো প্রস্থ অনুযায়ী সর্ট করুন (প্রস্থ সম হলে উচ্চতা ডিসেন্ডিং)۔
2. নেস্টেড রেক্ট্যাঙ্গেল ট্র্যাক করার জন্য nested ভেক্টর রাখুন।
3. সবচেয়ে বড় রেক্ট্যাঙ্গেল থেকে শুরু করে ছোটগুলোর জন্য বাইনারি সার্চ দিয়ে উপযুক্ত পজিশন খুঁজুন।
4. nested-এর সাইজই উত্তর।

C++ কোড

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

bool comp(const pair<int,int>& L, const pair<int,int>& R) {
    if (L.first == R.first) return L.second > R.second;
    return L.first < R.first;
}

int Rectangles(vector<pair<int,int>> &boxes) {
    int n = boxes.size();
    sort(boxes.begin(), boxes.end(), comp);
    vector<pair<int,int>> nested;
    nested.push_back(boxes[n-1]);
    for (int i=n-2; i>=0; --i) {
        int right = nested.size()-1, left = 0;
        while (left <= right) {
            int mid = (left+right)/2;
            if (nested[mid].first == boxes[i].first || nested[mid].second <= boxes[i].second)
                left = mid+1;
            else
                right = mid-1;
        }
        if (left == nested.size())
            nested.push_back(boxes[i]);
        else {
            nested[left].first = boxes[i].first;
            nested[left].second = boxes[i].second;
        }
    }
    return nested.size();
}

int main() {
    vector<pair<int,int>> boxes = {{30,45},{15,15},{45,30},{60,75}};
    cout << Rectangles(boxes); // Output: 2
}

ব্যাখ্যা

সর্টেড অর্ডারে প্রক্রিয়া করে বাইনারি সার্চ দিয়ে LIS-র মতো নেস্টিং চেইন বানানো হয়। nested ভেক্টর প্রতিটি চেইনের সর্বশেষ (সর্বোচ্চ) রেক্ট্যাঙ্গেল রাখে।