'''
Description: 
Autor: Au3C2
Date: 2021-03-05 10:50:46
LastEditors: Au3C2
LastEditTime: 2021-03-05 10:51:10
'''
class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        if not envelopes:
            return 0
        
        n = len(envelopes)
        envelopes.sort(key=lambda x: (x[0], -x[1]))

        f = [envelopes[0][1]]
        for i in range(1, n):
            if (num := envelopes[i][1]) > f[-1]:
                f.append(num)
            else:
                index = bisect.bisect_left(f, num)
                f[index] = num
        
        return len(f)

# 动态规划，困难。完全不想做
# https://leetcode-cn.com/problems/russian-doll-envelopes/