russian doll

import bisect
class :
    def maxEnvelopes(self, envelopes):
        """
        :type envelopes: List[List[int]]
        :rtype: int
        """
        if not envelopes:
            return 0
        l = len(envelopes)
        if l == 1:
            return 1
        
        envelopes.sort(key=lambda c:(c[0], -c[1]))
        # 此时再通过对长度做longest increasing sub-sequence就能求出解
        return self.lis(list(map(lambda c: c[1], envelopes)))
    
    def lis(self, arr):
        q = []
        for i in arr:
            pos = bisect.bisect_left(q, i)
            if len(q) == pos:
                q.append(i)
            else:
                q[pos] = i
        return len(q)