Prerequisite :- Sorting,Greedy.
Problem :- Given the dimensions of the available blocks, the task is to determine the height of the tallest pyramid Indraneel can build. He can reduce the length of the block from any edges to make them square.
The pyramid is constructed by placing square blocks of decreasing sizes on top of each other, ending with a 1x1 block at the top.
For Example, if Indraneel has rectangular blocks with dimensions 8x8, 2x8, 2x1, and 2x2, he can shave them to build a pyramid of height 3.
8x8 get shave to form 3x3
2x2 is already present
2x1 get shave to form 1x1
Explanation : -
Taking the Minimum of Both Dimensions:
Start by iterating through each rectangular block provided.
For each block, calculate the minimum of its two dimensions. This minimum represents the size of the largest square block that can be obtained from the rectangular block.
By taking the minimum of both dimensions, we ensure efficient use of wood, as the square block can be shaped without leaving any excess wood unused.
Sorting the Vector:
- After determining the minimum side length of each block, store these minimum side lengths in a vector.
- Sorting the vector in non-decreasing order facilitates systematic processing of the blocks.
- Sorting ensures that blocks with smaller minimum side lengths are considered first.
- Prioritizing blocks with smaller minimum side lengths maximizes the height of the pyramid, as smaller blocks can potentially fit into smaller spaces, allowing us to use more blocks in total.
Counting Maximum Height:
- We can use a greedy approach here by trying to build the pyramid from top. We will start from the smallest block and add new block only if it is larger than current. The larger blocks can always be shaved off to fit the constraints.
Initialize a variable cnt to 0, which represents the current maximum height of the pyramid that Indraneel can build. - Iterate through each element e in the sorted vector.
For each element e, if e is greater than cnt, it means that a block with side length e can be added to the pyramid, increasing the maximum height by 1. So, we increment cnt by 1. - This process continues until all blocks are considered, and cnt holds the maximum height of the pyramid.
C++ Solution:-
#include <bits/stdc++.h>
using namespace std;
int main() {
// your code goes here
int n;
cin >> n;
vector < int > v;
for (int i = 0; i < n; i++) {
int n1, n2;
cin >> n1 >> n2;
v.push_back(min(n1, n2));
}
sort(v.begin(), v.end());
int cnt = 0;
for (auto e: v) {
if (e > cnt) cnt++;
}
cout << cnt << "\n";
}