Russian Doll Envelopes

Sizga envelopes massivi berilgan, bunda envelopes[i] = [wi, hi] i-chi konvertning eni va balandligini bildiradi.

Bitta konvertni boshqa bir konvert ichiga joylashtirish uchun, ichkisining eni ham, balandligi ham tashqisidan qat'iy kichik bo'lishi shart.

Bir-birining ichiga joylashtirilishi mumkin bo'lgan maksimal konvertlar sonini qaytaring.

func solve(envelopes [][]int) int {
    // ...
}

Misollar

Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Tushuntirish: Konvertlarni eng ko'p [2,3] => [5,4] => [6,7] tartibida joylashtirish mumkin.

Input: envelopes = [[1,1],[1,1],[1,1]]
Output: 1

Input: envelopes = [[2,100],[3,200],[4,300],[5,500],[5,400],[5,250],[6,370],[6,360],[7,380]]
Output: 5

Maslahatlar

1. Bu masalani "Longest Increasing Subsequence" (eng uzun o'suvchi qism-ketma-ketlik) masalasiga aylantirish mumkin — buning uchun konvertlarni to'g'ri tartibda saralab olish kerak.
2. Konvertlarni eni bo'yicha o'sish tartibida, eni teng bo'lganda esa balandligi bo'yicha KAMAYISH tartibida saralang (bu bir xil enli konvertlarning bir-biriga tasodifan "ichma-ich" hisoblanib ketishining oldini oladi). Shundan so'ng faqat balandliklar ketma-ketligida eng uzun QAT'IY o'suvchi qism-ketma-ketlikni O(n log n) da (tails massivi va binar qidiruv bilan) toping.