1
# Runtime: 1587 ms (Top 72.81%) | Memory: 61.7 MB (Top 65.15%)
2

3
from bisect import bisect_left
4

5

6
class Solution:
7
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
8
        envelopes = sorted(envelopes, key=lambda x: (x[0], -x[1]))
9
        rst = []
10
        for _, h in envelopes:
11
            i = bisect_left(rst, h)
12
            if i == len(rst):
13
                rst.append(h)
14
            else:
15
                rst[i] = h
16
        return len(rst)