Interview question from the interwebz
You have a set of envelopes of different widths and heights. One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope. What is the maximum number of envelopes can you russian doll?
# assuming no dups def max_russian_doll(enve): if not enve: return 0 enve.sort() max_global = 1 for j in xrange(len(enve) - 1): max_local = 1 for i in xrange(j, len(enve) - 1): if enve[i] < enve[i + 1] and enve[i] != enve[i + 1]: # @comment max_local += 1 max_global = max(max_global, max_local) return max_global envelopes = [(4,5), (6,7), (2,3)] max_russian_doll(envelopes)
obviously this is \$O(n^2)\$. Right now I'm trying to figure out faster solution. Any tips?