j608. 4. 機器出租 - 高中生程式解題系統

Content

有 $N$ 個活動，舉辦每個活動都要租借一台機器，若要舉辦第 $i$ 個活動，就需要在時間段 $[L_i, R_i]$ 租借用一台機器的。

已知 $N$ 個活動的需要使用的時間段，並且有 $K$ 台機器可以開放租借，且一台機器同時間只能借給一個活動，請問最多可以成功舉辦多少場活動？

註：時間段 [2, 5] 與時間段 [5, 10] 的兩個活動無法使用同一台機器，因為兩台機器都需要用到時段 5

Input

第一行有兩個正整數 $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$

Output

輸出一個整數表示最多可以舉辦多少活動

Sample Input #1

5 1
0 2 1 3 4
2 3 5 4 6

Sample Output #1

Sample Input #2

8 2
3 1 4 3 7 2 2 5
5 3 7 4 8 7 4 6

Sample Output #2

Sample Input #3

2 1
1 2
2 3

Sample Output #3

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (5%): 1.0s , <1K
公開測資點#1 (5%): 1.0s , <1K
公開測資點#2 (5%): 1.0s , <1K
公開測資點#3 (5%): 1.0s , <1K
公開測資點#4 (5%): 1.0s , <1M
公開測資點#5 (5%): 1.0s , <1M
公開測資點#6 (5%): 1.0s , <1M
公開測資點#7 (5%): 1.0s , <1M
公開測資點#8 (5%): 1.0s , <1K
公開測資點#9 (5%): 1.0s , <10M
公開測資點#10 (5%): 1.0s , <1M
公開測資點#11 (5%): 1.0s , <1M
公開測資點#12 (5%): 1.0s , <10M
公開測資點#13 (5%): 1.0s , <10M
公開測資點#14 (5%): 1.0s , <10M
公開測資點#15 (5%): 1.0s , <10M
公開測資點#16 (5%): 1.0s , <10M
公開測資點#17 (5%): 1.0s , <10M
公開測資點#18 (5%): 1.0s , <10M
公開測資點#19 (5%): 1.0s , <10M

Hint ：

範例 1
可以選擇時間段是 [0, 2] 與 [3, 4] 的活動

範例 2
第一台機器服務時間段是 [1, 3] 與 [4, 7] 的活動
第二台機器服務時間段是 [2, 4], [5, 6] 與 [7, 8] 的活動

範例 3
兩個活動有重複的時間段，不能使用同一台機器

Tags:

APCS 排程問題貪心法

出處:

2023年1月 APCS [管理者： algo.seacow@gmail.com

algo.seacow@...(演算法海牛) ]

ID	User	Problem	Subject	Hit	Post Date
33653	a110608@ctes...(鍾均)	j608	C++ & Python 雙題解！(附完整解題過程&程式碼) (有40%解與AC解)	63	2023-01-18 18:25
33628	andyandy0828...(李小明)	j608	python詳解	48	2023-01-14 19:42
33538	willy633526@...(ByTech)	j608	40 分解法以及 AC 解法 (Python)	110	2023-01-12 01:32
33504	mushroom.cs9...(mushroom)	j608	題解	169	2023-01-10 22:35
33485	tojimmy0917@...(xTaiwanPingLord)	j608	C++ 解	278	2023-01-09 15:23