在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