j608.
4. 機器出租
內容
有 $N$ 個活動，舉辦每個活動都要租借一台機器，若要舉辦第 $i$ 個活動，就需要在時間段 $[L_i, R_i]$ 租借用一台機器的。
已知 $N$ 個活動的需要使用的時間段，並且有 $K$ 台機器可以開放租借，且一台機器同時間只能借給一個活動，請問最多可以成功舉辦多少場活動？
註：時間段 [2, 5] 與時間段 [5, 10] 的兩個活動無法使用同一台機器，因為兩台機器都需要用到時段 5
輸入說明
第一行有兩個正整數 $N$ 和 $K$
第二行有 $N$ 個正整數，第 $i$ 個正整數是活動 $i$ 的開始時間 $L_i$
第三行有 $N$ 個正整數，第 $i$ 個正整數是活動 $i$ 的結束時間 $R_i$
(20%) : $1 \leq N \leq 100, K=1$
(20%) : $1 \leq N \leq 100000, K=1$
(60%) : $1 \leq N \leq 100000, 1 \leq K \leq 100$
所有測試資料都滿足 $0 \leq L_i \leq R_i \leq 10^8$
輸出說明
輸出一個整數表示最多可以舉辦多少活動
範例輸入
#1
5 1 0 2 1 3 4 2 3 5 4 6
範例輸出
#1
2
範例輸入
#2
8 2 3 1 4 3 7 2 2 5 5 3 7 4 8 7 4 6
範例輸出
#2
5
範例輸入
#3
2 1 1 2 2 3
範例輸出
#3
1
測資資訊：
記憶體限制：
256
MB
提示 ：
範例 1
可以選擇時間段是 [0, 2] 與 [3, 4] 的活動
範例 2
第一台機器服務時間段是 [1, 3] 與 [4, 7] 的活動
第二台機器服務時間段是 [2, 4], [5, 6] 與 [7, 8] 的活動
範例 3
兩個活動有重複的時間段，不能使用同一台機器
出處:
2023年1月APCS
[管理者：
algo.seacow@
...
(演算法海牛)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 41045 |
|
j608 | 219 | 2024-06-28 11:49 | |
| 37432 |
|
j608 | 927 | 2023-09-08 11:50 | |
| 36787 | fire5386 (becaidorz) | j608 | 599 | 2023-08-08 15:12 | |
| 36052 |
|
j608 | 564 | 2023-07-01 23:46 | |
| 35423 |
|
j608 | 541 | 2023-06-01 22:10 |