C++ এ একটির মধ্যে আরেকটি ঢোকানোর পর অবশিষ্ট আয়তক্ষেত্রের ন্যূনতম সংখ্যা খুঁজুন

ধরুন আমাদের N বিভিন্ন আয়তক্ষেত্রের প্রস্থ এবং উচ্চতা আছে; একটির মধ্যে আরেকটি ঢোকানোর পর আমাদের ন্যূনতম সংখ্যক আয়তক্ষেত্র বাকি আছে তা খুঁজে বের করতে হবে। সুতরাং, যদি W1 এবং W2 যথাক্রমে R1 এবং R2 আয়তক্ষেত্রের প্রস্থ হয়। এবং H1 এবং H2 যথাক্রমে R1 এবং R2 এর উচ্চতা, তারপর যদি W1

সুতরাং, যদি ইনপুটটি হয় {{ 30, 45 }, { 15, 15 }, { 45, 30 },{60, 75 }}, তাহলে আউটপুট হবে 2 কারণ সম্ভাব্য উপায়গুলির মধ্যে একটি হল দ্বিতীয় আয়তক্ষেত্র সন্নিবেশ করানো প্রথমটিতে এবং তারপর চতুর্থটিতে সেই আয়তক্ষেত্রটি সন্নিবেশ করান। তৃতীয় এবং চতুর্থ আয়তক্ষেত্র বাকি।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• n :=বাক্সের আকার

• অ্যারে বাক্সগুলিকে তাদের আকারের উপর ভিত্তি করে সাজান

• জোড়ার নেস্টেড একটি অ্যারে সংজ্ঞায়িত করুন

• নেস্টেডের শেষে বক্সগুলি [n - 1] ঢোকান

• আরম্ভ করার জন্য i :=n - 2, যখন i>=0, আপডেট করুন (i 1 দ্বারা কম করুন), −

  • ডান:=নেস্টেডের আকার

  • যখন বামে <=ডানে, কর:

    • মধ্য :=(ডান + বাম) / 2

    • যদি নেস্টেড[মিড] এর উচ্চতা বাক্সের উচ্চতা [i] বা নেস্টেডের প্রস্থ [মিড] <=বাক্সগুলির প্রস্থ [i] সমান হয়, তাহলে −

      • বাম :=মধ্য + 1

    • অন্যথায়

      • ডান:=মধ্য - 1

  • বাম যদি নেস্টেডের আকারের সমান হয়, তাহলে −

    • নেস্টেডের শেষে বক্সগুলি [i] সন্নিবেশ করুন

  • অন্যথায়

    • নেস্টেডের প্রস্থ [বাম] :=বাক্সগুলির প্রস্থ[i]

    • নেস্টেডের উচ্চতা [বাম] :=বাক্সের উচ্চতা[i]

• নেস্টেডের রিটার্ন সাইজ

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#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 = (right + left) / 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].second = boxes[i].second;
         nested[left].first = boxes[i].first;
      }
   }
   return nested.size();
}
int main() {
   vector<pair<int, int>> boxes = {{30, 45}, {15,15}, {45,30},{60,75}};
   cout << Rectangles(boxes);
}

ইনপুট

{{30, 45}, {15,15}, {45,30},{60,75}}

আউটপুট

2