[LeetCode] 354. Russian Doll Envelopes

😎풀이

1. envelopes 너비 기준 오름차 순, 높이 기준 내림차 순 정렬
   1-1. 다음 봉투는 이전 봉투를 포함할 수 있어야 함
   1-2. 높이를 오름차 순 정렬할 경우, 동일 너비의 봉투도 포함 가능하다는 의미로 잘못 해석됨
2. 정렬된 봉투 순회
   2-1. 해당 봉투가 몇 번째로 포함될지 탐색
   2-2. 해당 봉투가 가장 큰 경우 새로 추가
3. 봉투가 최대 몇 겹인지 반환

function maxEnvelopes(envelopes: number[][]): number {
    const sorted = envelopes.toSorted(([aw, ah], [bw, bh]) => {
        if(aw !== bw) return aw - bw
        return bh - ah
    })
    const lis = []
    for(const [, h] of sorted) {
        let left = 0
        let right = lis.length
        while(left < right) {
            const mid = Math.floor((left + right) / 2)
            if(lis[mid] < h) left = mid + 1
            else right = mid
        }
        if(lis.length === left) lis.push(h)
        else lis[left] = h
    }
    return lis.length
};