LeetCode: 354. Russian Doll Envelopes

매우 어려운 문제였다.

다만 아래 문제를 먼저 풀면, 이 문제도 쉽게 풀 수 있다.

https://focalpoint.tistory.com/179

LeetCode: 300. Longest Increasing Subsequence - 시바견의 끄적임

from bisect import bisect_left
class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        envelopes.sort(key=lambda x: (x[0], -x[1]))
        dp = [envelopes[0][1]]
        for i in range(1, len(envelopes)):
            idx = bisect_left(dp, envelopes[i][1])
            if idx == len(dp):
                dp.append(envelopes[i][1])
            else:
                dp[idx] = envelopes[i][1]
        return len(dp)