APCS202301第4題機器出租

zerojudge網址：https://zerojudge.tw/ShowProblem?problemid=j608


解題策略：排序+multiset+二分搜尋(lower_bound)

活動依照結束時間由小到大排序，若結束時間相同，可以不用依照開始時間排序。機器結束時間依序加入multiset會形成平衡的binary search tree，使用二分搜尋lower_bound找出第一個iterator(it)大於等於新活動的開始時間，(--it)就會找到最後一個機器結束時間小於新活動開始時間的機器，該機器執行新活動，更新結束時間到multiset。

範例輸入 #1

5 1

0 2 1 3 4

2 3 5 4 6

範例輸出 #1

2


範例輸入 #3

2 1

1 2

2 3

範例輸出 #3

1

範例輸入 #2

8 2

3 1 4 3 7 2 2 5

5 3 7 4 8 7 4 6

範例輸出 #2

5

C++參考程式

Python程式碼(使用bisect取代multiset)