Largest subset of rectangles such that no rectangle fit in any other rectangle | Recursive function to get the largest subset ; Base case when it exceeds ; If the state has been visited previously ; Initialize ; No elements in subset yet ; First state which includes current index ; Second state which does not include current index ; If the rectangle fits in , then do not include the current index in subset ; First state which includes current index ; Second state which does not include current index ; Function to get the largest subset ; Sort the array ; Get the answer ; Driver code ; ( height , width ) pairs
def findLongest ( a , n , present , previous ) : NEW_LINE INDENT if present == n : NEW_LINE INDENT return 0 NEW_LINE DEDENT elif previous != - 1 : NEW_LINE INDENT if dp [ present ] [ previous ] != - 1 : NEW_LINE INDENT return dp [ present ] [ previous ] NEW_LINE DEDENT DEDENT ans = 0 NEW_LINE if previous == - 1 : NEW_LINE INDENT ans = 1 + findLongest ( a , n , present + 1 , present ) NEW_LINE ans = max ( ans , findLongest ( a , n , present + 1 , previous ) ) NEW_LINE DEDENT else : NEW_LINE INDENT h1 = a [ previous ] [ 0 ] NEW_LINE h2 = a [ present ] [ 0 ] NEW_LINE w1 = a [ previous ] [ 1 ] NEW_LINE w2 = a [ present ] [ 1 ] NEW_LINE if h1 <= h2 and w1 <= w2 : NEW_LINE INDENT ans = max ( ans , findLongest ( a , n , present + 1 , previous ) ) NEW_LINE DEDENT else : NEW_LINE INDENT ans = 1 + findLongest ( a , n , present + 1 , present ) NEW_LINE ans = max ( ans , findLongest ( a , n , present + 1 , previous ) ) NEW_LINE DEDENT DEDENT dp [ present ] [ previous ] = ans NEW_LINE return ans NEW_LINE DEDENT def getLongest ( a , n ) : NEW_LINE INDENT a . sort ( ) NEW_LINE ans = findLongest ( a , n , 0 , - 1 ) NEW_LINE return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT a = [ [ 1 , 5 ] , [ 2 , 4 ] , [ 1 , 1 ] , [ 3 , 3 ] ] NEW_LINE N = 10 NEW_LINE dp = [ [ - 1 for i in range ( N ) ] for j in range ( N ) ] NEW_LINE n = len ( a ) NEW_LINE print ( getLongest ( a , n ) ) NEW_LINE DEDENT