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}}
출력
2