P-4-14. 控制點 (2D-max)
平面上有 \( N \) 個點,第 \( i \) 點的座標為 \((x[i]\) , \( y[i])\) 。若 \( x[i]≤x[j] \) 且 \( y[i]≤y[j]\) ,則我們說第 \( j \) 點可以控制第 \( i \) 點。我們希望能在輸入的點中,選取最少的點做為控制點,使得每一個輸入的點都至少被一個控制點所控制。 輸入 \( N \) 個點的座標,請計算出最少要選取多少個控制點。
輸入格式
每筆測試資料的第一行為一個正整數 \( N,N\) \( \)<=\( \) \(1e5\) 。 第二行有 \( N \) 個非負整數,依序是這些點的 \( X \) 座標, 第三行有 \( N \) 個非負整數,依序是這些點的 \( Y \) 座標, 座標值不超過 \( 1e9\) 。
輸出格式
輸出最少的控制點數量。
範例輸入一
4
1 2 3 3
1 2 3 3
範例輸出一
1
範例輸入一
8
3 1 5 3 4 7 8 9
8 2 5 1 2 4 2 3
範例輸出一
4
留言