# APCS實作題2023年1月第4題：機器出租

> 日期：2024年8月14日
> 作者：王一哲
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=j608)

## 題目

### 問題描述

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

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

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

### 輸入說明

第一行有兩個正整數 $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,~ K = 100$

所有測試資料都滿足 $0 \leq L_i, R_i \leq 10^8$

<br />

### 輸出格式

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

### 範例輸入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

### 範例輸出2

1

<br /><br />

## Python 程式碼

基本原則：
1. 活動越早結束，可以使用的機器越多。
2. 如果結束時間相同，優先選擇比較晚開始的活動，這樣使用機器的時間比較短，

為了達到這個要求，需要用第4 ~ 9行的自訂比較式，配合第15行的 cmp_to_key 將資料排序。
費時最久約為 1 s，使用記憶體最多約為 38.1 MB，通過測試。

from bisect import bisect_left
from functools import cmp_to_key

def mycmp(a, b):  # 排序用的比較式，輸入 (開始時間, 結束時間)
    if a[1] == b[1]:  # 如果結束時間相同，依照開始時間由大到小排序
        if a[0] < b[0]: return 1  # 符合條件的項往後放
        else: return -1
    if a[1] > b[1]: return 1  # 否則依照結束時間由小到大排序
    else: return -1

N, K = map(int, input().split())  # 讀取 N、K
ls = list(map(int, input().split()))  # 讀取開始時間
le = list(map(int, input().split()))  # 讀取結束時間
se = list(zip(ls, le))  # 兩者組成串列
se.sort(key = cmp_to_key(mycmp))  # 排序
#print(se)
cnt = [-1]*K  # 計錄使用中機器的結束時間，預設為 -1
ans = 0  # 答案，預設為 0
for s, e in se:  # 由 se 依序讀取開始時間 s、結束時間 e
    idx = bisect_left(cnt, s)  # 找出 cnt 之中插入 s 的索引值
    if idx == 0: continue  # 如果 idx == 0，沒有可以使用的機器，找下一項
    del cnt[idx-1]  # 用 del 刪除前一項
    cnt.append(e)  # 將結束時間加入 cnt
    ans += 1  # 數量加 1
    #print(cnt)
print(ans)  # 印出答案

<br /><br />

## C++ 程式碼

費時最久約為 55 ms，使用記憶體最多約為 1.1 MB，通過測試。

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

bool mycmp(pair<int, int> a, pair<int, int> b) {  // 排序用的比較式，輸入 (開始時間, 結束時間)
    if (a.second == b.second) return a.first > b.first;  // 如果結束時間相同，依照開始時間由大到小排序
    return a.second < b.second;  // 否則依照結束時間由小到大排序
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);  // 加速
    int N, K; cin >> N >> K;  // 讀取 N、K
    vector<pair<int, int>> se (N, make_pair(0, 0));  // 長度為 N 的二維陣列，儲存開始、結束時間
    for(int i=0; i<N; i++) cin >> se[i].first;  // 讀取開始時間
    for(int i=0; i<N; i++) cin >> se[i].second;  // 讀取結束時間
    sort(se.begin(), se.end(), mycmp);  // 排序
    vector<int> cnt (K, -1);  // 計錄使用中機器的結束時間，預設為 -1
    int ans = 0;  // 答案，預設為 0
    for(auto v : se) {  //  由 se 依序讀取資料
        int s = v.first, e = v.second;  // 開始時間 s、結束時間 e
        int idx = lower_bound(cnt.begin(), cnt.end(), s) - cnt.begin();  // 找出 cnt 之中插入 s 的索引值
        if (idx == 0) continue;  // 如果 idx == 0，沒有可以使用的機器，找下一項
        cnt.erase(cnt.begin() + idx - 1);  // 用 erase 刪除前一項
        cnt.push_back(e);  // 將結束時間加入 cnt
        ans++;  // 數量加 1
    }
    cout << ans << "\n";  // 印出答案
    return 0;
}

<br /><br />

---

###### tags:`APCS`、`Python`、`C++`