在C ++中将一个矩形插入另一个矩形后，找到剩余的最小矩形数

假设我们有N个不同矩形的宽度和高度；我们必须找到将一个矩形插入另一个矩形后剩余的最小矩形数。因此，如果W1和W2分别是矩形R1和R2的宽度。并且H1和H2分别为R1和R2的高度，则如果W1 <W2和H1 <H2，则矩形R1可以容纳在矩形R2内。因此，最小的一个可以适合第二个最小的，然后适合另一个，依此类推。

因此，如果输入类似于{{30，45}，{15，15}，{45，30}，{60，75}}，则输出将为2，因为可能的方法之一是插入第二个矩形插入第一个，然后将该矩形插入第四个。左边的第三个和第四个矩形。

为了解决这个问题，我们将遵循以下步骤-

• n：=盒子大小

• 根据数组框的大小对其进行排序

• 定义一个嵌套对的数组

• 在嵌套末尾插入框[n-1]

• 对于初始化i：= n-2，当i> = 0时，更新（将i减1），执行-

• nested [left]的宽度：=盒子的宽度[i]

• nested [left]的高度：=盒子的高度[i]

• 在嵌套的末尾插入box [i]

• 中：=（右+左）/ 2

• 如果nested [mid]的高度与boxs [i]的高度相同或nested [mid]的宽度<= boxs [i]的宽度，则-

• 除此以外

• 左：=中+ 1

• 右：=中-1

• 右：=嵌套的大小

• 左<=右时，请执行以下操作：

• 如果左与嵌套的大小相同，则-

• 除此以外

• 返回嵌套的大小

例 

让我们看下面的实现以更好地理解-

#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