数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 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 := 盒子的数量
根据大小对数组 boxes 进行排序
定义一个存储对的数组 nested
将 boxes[n - 1] 插入到 nested 的末尾
对于初始化 i := n - 2，当 i >= 0 时，更新（i 减 1），执行以下操作：
right := nested 的大小
当 left <= right 时，执行以下操作：
mid := (right + left) / 2
如果 nested[mid] 的高度与 boxes[i] 的高度相同，或者 nested[mid] 的宽度 <= boxes[i] 的宽度，则：
left := mid + 1
否则
right := mid - 1
如果 left 等于 nested 的大小，则：
将 boxes[i] 插入到 nested 的末尾
否则
nested[left] 的宽度 := boxes[i] 的宽度
nested[left] 的高度 := boxes[i] 的高度
返回 nested 的大小
示例
让我们看看以下实现以更好地理解：
#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
155 次查看
