假设我们有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