直升機抓寶 (AP325 Q-6-23)

小智的學校在天空之城，他每天開直升機上學，現在他想要規劃一條路徑以便在從家裡到學校的路上可以抓到最多的寶貝，請你寫個程式幫助他。

我們將學校與他家之間所有的位置劃分成 \(N \times N\) 的格子，每個格子以座標 \((x, y)\) 表示，其中 \(x\) 代表水平距離，\(y\) 代表高度，而小智家的座標在 \((0, 0)\) 的位置，學校在 \((N-1, N-1)\) 的位置。由於他的父母不准他上學途中貪玩繞路，直升機被設定成每次只能向前或向上一格，也就是說，只能從 \((x, y)\) 到 \((x+1, y)\) 或 \((x, y+1)\)；當然，他也不可以超過 \(x < N\) 且 \(y < N\) 的範圍，否則會無法到達學校。

小智到學校的路途上一共有 \(N\) 隻寶貝，每隻寶貝可以捕獲的範圍是某特定高度而水平座標在某連續區間的格子。明確的說，對於寶貝 \(P(i)\)，\(0 \le i < N\)，要捕捉到 \(P(i)\)，小智必須經過下列座標之一：\(\{(x, y) \mid S(i) \le x \le T(i) \text{ 且 } y = i\}\)，其中所有的 \(S(i)\) 與 \(T(i)\) 都已經透過抓寶雷達得到資料了。

上圖是一個 \(N = 5\) 的例子，藍色區塊顯示可以捕捉到寶貝的地方，請注意，每一個寶貝都是在一個水平連續區間。紅線所顯示的路徑是一條合乎規定的路徑，因為他每一步都只有向右或向上，沿這一條路徑可以捕捉到四隻寶貝，是所有可能路徑中可以捕捉到寶貝數最多的。

輸入格式

第一行是座標範圍的 \(N\)，接下來 \(N\) 行，每一行有兩個整數 \(S(i)\) 與 \(T(i)\)，依序是 \(i = 0, 1, \ldots, N-1\)。

限制

• \(1 \le N \le 2.5 \times 10^5\)。
• \(0 \le S(i) \le T(i) < N\)。

輸出格式

輸出最多可能抓到的寶貝數。

評分說明

每筆計分測資獨立計分，每筆 5 分，共 100 分；範例不計分。

範例輸入 1

5
1 3
0 1
3 4
0 0
2 3

範例輸出 1

4

範例輸入 2

2
1 1
0 0

範例輸出 2

1

題目來源

本題出自中正大學吳邦一教授所著《AP325－從 APCS 實作題檢測三級到五級》（v1.5）第 6 章 Q-6-23，第 213 頁；經作者同意於 AACPOJ 免費公開。原題出自 105 學年度全國高級中等學校資訊學科能力競賽。教材下載：AP325 講義（Google Drive）；Python 版：AP325-Python（HackMD）。