C++で長方形を挿入した後に残っている長方形の最小数を見つけます

したがって、入力が{{30、45}、{15、15}、{45、30}、{60、75}}のような場合、2番目の長方形を挿入する方法の1つとして、出力は2になります。最初の長方形に挿入し、次にその長方形を4番目の長方形に挿入します。左の3番目と4番目の長方形。

これを解決するには、次の手順に従います-

• n：=ボックスのサイズ

• サイズに基づいて配列ボックスを並べ替える

• ペアのネストされた配列を定義する

• ネストされた最後にボックス[n-1]を挿入します

• 初期化i：=n-2の場合、i> =0の場合、更新（iを1つ減らす）、実行-

  • 右：=ネストされたサイズ

  • 左<=右、実行：

    • mid：=（右+左）/ 2

    • ネストされた[mid]の高さがboxes[i]の高さまたはnested[mid]の幅<=ボックスの幅[i]と同じである場合、-

      • 左：=半ば+ 1

    • それ以外の場合

      • 右：=半ば-1

  • 左がネストされたサイズと同じである場合、-

    • ネストされた最後にboxes[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