Russian Doll Envelopes

Problem: Russian Doll Envelopes

First we sort the envelopes and if the width are the same, we put the envelopes with bigger height at first so that we can wrap more previous envelopes. Then we go through the sorted envelopes and try to wrap them. Every time we try to wrap them most compact so that we can wrap more latter envelopes.

Code in Python:

class Solution(object):
    def maxEnvelopes(self, envs):
        """
        :type envelopes: List[List[int]]
        :rtype: int
        """
        def liss(envs):
            def lmip(envs, tails, k):
                b, e = 0, len(tails) - 1
                while b <= e:
                    m = (b + e) >> 1
                    if envs[tails[m]][1] >= k[1]:
                        e = m - 1
                    else:
                        b = m + 1
                return b

            tails = []
            for i, env in enumerate(envs):
                idx = lmip(envs, tails, env)
                if idx >= len(tails):
                    tails.append(i)
            return tails


        def f(x, y):
            return -1 if (x[0] < y[0] or x[0] == y[0] and x[1] > y[1]) else 1

        envs.sort(cmp=f)
        return liss(envs)