在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
    猜你喜欢