Maximum number of plates that can be placed from top to bottom in increasing order of size | C ++ Program for the above approach ; Comparator function to sort plates in decreasing order of area ; Recursive function to count and return the max number of plates that can be placed ; If no plate remains ; If length and width of previous plate exceeds that of the current plate ; Calculate including the plate ; Calculate excluding the plate ; Otherwise ; Calculate only excluding the plate ; Driver code ; Sorting plates in decreasing order of area ; Assuming first plate to be of maximum size
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool comp ( vector < int > v1 , vector < int > v2 ) { return v1 [ 0 ] * v1 [ 1 ] > v2 [ 0 ] * v2 [ 1 ] ; } int countPlates ( vector < vector < int > > & plates , int lastLength , int lastWidth , int i , int n ) { if ( i == n ) return 0 ; int taken = 0 , notTaken = 0 ; if ( lastLength > plates [ i ] [ 0 ] && lastWidth > plates [ i ] [ 1 ] ) { taken = 1 + countPlates ( plates , plates [ i ] [ 0 ] , plates [ i ] [ 1 ] , i + 1 , n ) ; notTaken = countPlates ( plates , lastLength , lastWidth , i + 1 , n ) ; } else notTaken = countPlates ( plates , lastLength , lastWidth , i + 1 , n ) ; return max ( taken , notTaken ) ; } int main ( ) { vector < vector < int > > plates = { { 6 , 4 } , { 5 , 7 } , { 1 , 2 } , { 3 , 3 } , { 7 , 9 } } ; int n = plates . size ( ) ; sort ( plates . begin ( ) , plates . end ( ) , comp ) ; int lastLength = INT_MAX ; int lastWidth = INT_MAX ; cout << countPlates ( plates , lastLength , lastWidth , 0 , n ) ; return 0 ; }