d056. P_4_14 控制點(2D-max)

Content

平面上有 $N$ 個點，第 $i$ 點的座標為 $(x[i], y[i])$。若 $x[i] ≤ x[j]$ 且 $y[i] ≤ y[j]$，則我們說第 $j$ 點可以控制第 $i$ 點。我們希望能在輸入的點中，選取最少的點做為控制點，使得每一個輸入的點都至少被一個控制點所控制。輸入 $N$ 個點的座標，請計算出最少要選取多少個控制點。

Input

每筆測試資料的第一行為一個正整數 $N$ ，$N ≤ 10^5$ 。

第二行有 $N$ 個非負整數，依序是這些點的 $X$ 座標，

第三行有 $N$ 個非負整數，依序是這些點的 $Y$ 座標，座標值不超過 $10^9$。

Output

輸出最少的控制點數量。

Sample Input #1

4
1 2 3 3
1 2 3 3

Sample Output #1

Sample Input #2

8
3 1 5 3 4 7 8 9
8 2 5 1 2 4 2 3

Sample Output #2

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (16%): 1.0s , <10M
公開測資點#1 (16%): 1.0s , <10M
公開測資點#2 (17%): 1.0s , <10M
公開測資點#3 (17%): 1.0s , <10M
公開測資點#4 (17%): 1.0s , <10M
公開測資點#5 (17%): 1.0s , <10M

Hint ：

Tags:

ch4

出處:

Prof. Wu [管理者：

ktlai (K．我已霸榜．Tlai)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」