C++에서 사각형을 다른 사각형에 삽입한 후 남은 사각형의 최소 수 찾기

N개의 다른 직사각형의 너비와 높이가 있다고 가정합니다. 직사각형을 다른 직사각형에 삽입한 후 남은 직사각형의 최소 수를 찾아야 합니다. 따라서 W1 및 W2가 각각 직사각형 R1 및 R2의 너비인 경우. 그리고 H1과 H2는 각각 R1과 R2의 높이이고, W1

따라서 입력이 {{ 30, 45 }, { 15, 15 }, { 45, 30 },{60, 75 }}와 같은 경우 출력은 2가 됩니다. 가능한 방법 중 하나는 두 번째 직사각형을 삽입하는 것입니다. 첫 번째에 사각형을 삽입한 다음 네 번째에 해당 사각형을 삽입합니다. 세 번째와 네 번째 사각형이 남습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=상자 크기
크기에 따라 배열 상자 정렬
쌍으로 중첩된 배열 정의
중첩된
끝에 상자[n - 1] 삽입
initialize i :=n - 2의 경우 i>=0일 때 업데이트(i를 1만큼 감소), −
- 오른쪽 :=중첩된 크기
- 왼쪽 <=오른쪽 동안 수행:
  - 중간 :=(오른쪽 + 왼쪽) / 2
  - 중첩[mid]의 높이가 상자[i]의 높이 또는 중첩[mid]의 너비 <=상자의 너비[i]와 같으면 -
    - 왼쪽 :=중간 + 1
  - 그렇지 않으면
    - 오른쪽 :=중간 - 1
- 왼쪽이 중첩된 크기와 같으면 -
  - 중첩된
    끝에 상자[i] 삽입
- 그렇지 않으면
  - 중첩 너비[left] :=상자 너비[i]
  - 중첩 높이[left] :=상자 높이[i]
중첩된 크기 반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#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}}