Today's Challenge

https://leetcode.com/problems/russian-doll-envelopes/

Russian Doll Envelopes - LeetCode

단순 x, y 값 비교만 하면 되는 줄 알았는데.. 결국 LIS 문제였구만 ㅠㅠ
그래도 BOJ에서 LIS는 티어가 낮은 편인데 여기선 꽤 높군.
bi_sect를 사용하는 건 처음 봄.

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