TypeScript 実装の各処理について、図解とともに詳細な解析を行います。 問題は「2次元の箱ネスト問題」ですが、これは**2次元 LIS（最長増加部分列）**に帰着できます。

箱 A が箱 B に入るには：

A.X < B.X かつ A.Y < B.Y

回転不可。 つまり、「縦・横ともに小さい箱は、縦・横ともに大きい箱の中に入れられる」。

1. X 昇順、Y 降順にソート
2. Y の LIS（最長増加部分列）を求める（Y方向に何個ネストできるか）

5
30 50
10 30
40 10
50 20
40 60

各箱を (X, Y) と表記します：

[30, 50], [10, 30], [40, 10], [50, 20], [40, 60]

• X 昇順
• 同じ X のときは Y 降順

boxes.sort((a, b) => {
    if (a[0] === b[0]) return b[1] - a[1]; // Y降順
    return a[0] - b[0]; // X昇順
});

[10, 30]
[30, 50]
[40, 60]  ← Y降順なので先
[40, 10]
[50, 20]

• 同じ X の中で Y が小さい方を後に回すことで、「X が同じ場合に複数の箱がネストされる誤り」を防ぐため。

• 与えられた数列から「単調増加の部分列」で最大の長さを求める。
• LISにより「最大ネスト数」が求まる。

[30, 50, 60, 10, 20]

LIS を構築する様子を図解します。

lis = []

• lis は空 → 30 を push

lis = [30]

• 50 > 30 → push

lis = [30, 50]

• 60 > 50 → push

lis = [30, 50, 60]

• 10 < 30 → 二分探索で差し替え（最初の位置）

lis = [10, 50, 60]

• 20 > 10 && < 50 → 2番目に差し替え

lis = [10, 20, 60]

• 長さは 3 → 最大ネスト数 = 3

例えば Y = 20 のとき、lis = [10, 50, 60] に対して：

binarySearch(lis, 20)
↓
mid = 1 → lis[1] = 50 > 20 → right = 1
mid = 0 → lis[0] = 10 < 20 → left = 1
→ 差し替え位置 = 1

• LIS により、常に「Y が昇順」なネストを構築する
• Xはソート済なので、Xの条件は保証されている
• Yは単調増加でなければならない → 最長長さを求めることでネスト数を最適化

console.log(result); // → 3

ソート後の箱:
(10,30) → (30,50) → (40,60) → (40,10) → (50,20)

対象Y:    30     →   50     →   60     →   10     →   20
LIS処理: [30]   → [30,50] → [30,50,60] → [10,50,60] → [10,20,60]
最長長さ: 3

• 箱ネスト問題は「2次元 LIS」として解ける
• ソート + 二分探索で O(N log N) を達成可能
• メモリ制約内（最大 N = 100000）でも高速・安全に動作