# [APCS] 工作排程

###### tags: `APCS`
## 題目
### 問題描述
有 $M$ 個工作要在 $N$ 台機器上加工，每個工作 $i$ 包含若干個工序 $o_{ij}$，這些工序必須依序加工，也就是前一道工序 $o_{i(j-1)}$ 完成後才可以開始下一道工序 $o_{ij}$。每一道工序 $o_{ij}$ 可以用一個有序對 $(k_{ij}, t_{ij})$ 來 表示它需要在機器 $k_{ij}$ 上面花費 $t_{ij}$ 小時來完成。**每台機器一次只能處理一道工序**。

所謂一道工序 $o_{ij}$ 的**最早完成時間** $c_{ij}^{*}$ 是指，考慮目前排程中機器 $k_{ij}$ 之可用性以及前一道工序 $o_{i(j-1)}$（如果該工序存在）之完成時間後可得的最早完成時間。
$$
c_{ij}^{*} = \max(機器k_{ij}最早可用時間, c_{i(j-1)}^{*}) + t_{ij}
$$

工廠經理安排所有工序的排程規則如下：
> 針對每一個工作的第一個尚未排程的工序，計算出此工序的**最早完成時間**，然後挑選出最早完成時間最小的工序納入排程，如果有多個最早完成時間都是最小，則挑選其中工作編號最小之工序。一個工序一旦納入排程就不會再更改。重複以上步驟直到所有工序皆納入排程。

我們總是從時間 0 開始排程。每個工作的完成時間為其最後一個工序的完成時間，本題的目標是計算出每個工作的完成時間並輸出其總和。

以下以一個例子來說明，在此例中有三個工作要在三台機器上排程，各工作的資料如下：
排程的過程說明如下：
1. 在開始時，每個工作都是考慮第一道工序，三個工作的第 1 道工序需要的時間分別是 $t_{11} = 4$、$t_{21} = 2$、$t_{31} = 7$，這也是它們的最早完成時間，也就是 $c_{11}^*=4$、$c_{21}^*=2$、
$c_{31}^*=7$，因此會先排 $o_{21}$。
2. 接下來，三個工作要考慮的工序分別是第1、2、1個工序，即 $o_{11}$、$o_{22}$ 和 $o_{31}$。
* $o_{11}$ 需要機器 2 執行 4 小時 ，而機器 2 可以開始加工的時間點是 0。$o_{11}$沒有前一道工序。因此，這工序可以開始的時間是 $\max(0, 0) = 0$。因此，其最早完成時間 $c_{11}^*= \max(0, 0) + 4 = 4$。
* $o_{22}$ 需要機 器 2 執行 2 小時，而機器 2 可以開始加工的時間點是 0。$o_{22}$ 前一道工序 $o_{21}$ 的完成時間是 2。因此，這工序可以開始的時間是 $\max(0, 2) = 2$。因此，其最早完成時間 $c_{22}^* = \max(0, 2) + 2 = 4$。
* $o_{31}$ 需要機器 0 執行 7 小時，而機器 0 可以開始加工的時間點是 2。$o_{31}$ 沒有前一道工序。因此，這工序可以開始的時間是 $\max(2, 0) = 2$。因此，其最早完成時間 $c_{31}^* = \max(2, 0) + 7 = 9$。因此，由於 $c_{11}^*$ 和 $c_{22}^*$ 都是最小，根據規則工作編號小的先排，所以會排 $o_{11}$。
3. 三個工作目前要考慮的工序分別第 2、2、1個工序。依照類似的推論，我們可以得到 $c_{12}^* = 5$、$c_{22}^* = 6$、$c_{31}^* = 9$，因此排 $o_{12}$。工作 1 的工序均已排完，所以它的完成時間是 5。
4. 剩下工作 2 與 3。$c_{22}^* = 6$、$c_{31}^* = 9$，因此先排 $o_{22}$。
5. $c_{23}^* = 7$ 而 $c_{31}^* = 9$，因此排 $o_{23}$，工作 2 的工序已排完，所以它的完成時間是 7。
6. 剩下工作 3，因為機器 0 的下一個可以開始時間是 7，故 $o_{31}$ 的完成時間是 $7+7=14$。

三個工作的完成時間分別是5、7、14，所以最後輸出答案 $5+7+14=26$。

### 輸入格式
第一行有兩個整數 $N$ 與 $M$，代表總共有 $N$ 台機器與 $M$ 個工作。接下來有 $M$ 個工作的資訊，輸入的順序即是工作編號順序。每個工作資訊包含兩行，第一行是整數 $P$，代表該工作的工序的數量；第二行是 $2 \cdot P$ 個整數，每兩個一組依序代表一道工序的機器編號與需求時間。

機器的編號由 0 開始。參數 $N$、$M$、$P$ 以及每個工序的需求時間都是不超過 100 的正整數。

### 輸出格式
輸出所有工作的完成時間的總和。


## 解答
### 題目分析

這個題目看起來題目敘述很長，題目又涉及似乎很高深的工作排程，或許讓一些人望之卻步。其實題目敘述本身不長，是例子的說明比較長，而APCS的考試不會要求基本數學以外的背景知識，所以這個題目完全不需要擔心不懂排程的背景知識。這種題目是屬於模擬題，題目中會敘述一個流程，希望你模擬這個流程來計算某些數值。模擬題的重點是**設定適當的變數記錄某些狀態，根據流程來逐步更新這些狀態**。

在本題中，有 $M$ 個工作與 $N$ 台機器，每個工作有數個工序 (task) 必須依序進行，每個 task 需要某台特定機器 以及需要若干時間，最重要的流程就是安排 task 的規則：
針對每一個工作的第一個尚未排程的工序，計算出此工序的最早完成時間，然後挑選出最早完成時間最小的工序納入排程，如果有多個最早完成時間都是最小，則挑選其中工作編號最小之工序。

對於每一個工作，它的下一個 task 的最早完成時間是什麼呢？應該是**這個 task 可以開始的時間，加上它所需要的時間**。那麼，它可以開始的時間又是什麼呢？依據定義它必須在它的前一個 task 完成後才能開始，而且它所需要的機器必須是空下來的。所以，在模擬的過程，除了輸入的資料之外，我們必須去記錄：
* 對每一個工作 $i$，下一個要安排的 task：`curr_task[i]`
* 對每一個工作 $i$，前一個 task 的完成時間：`prev_fin[i]`
* 對於每一個機器 $j$，下一個可以開始的時間：`avl[j]`

### 方法與流程
程式的架構其實很簡單，用一個迴圈每次安排一個 task，直到所有 task 都安排完畢。迴圈中，計算每一個工作下一個 task 的可能最早完成時間，並且找出最小值。找到之後，將此 task 排入機器，並更新機器與工作的狀態。程式架構如下：
迴圈內每次尋找 task 最早完成時間的最小值的時候，我們都重新計算，事實上，利用優先佇列(priority queue) 或類似資料結構，可以更有效率地完成此事。

### 程式實作

##### 輸入資料處理部分 #####
# 吃第一行輸入資料
# 包含機器(machine)數量n_machine
# 和工作(job)數量n_job
n_machine, n_job = map(int, input().split())

# 為每個job初始化一個裝數對的list
# 這些list再組成一個list of list
job = [[] for _ in range(n_job)]

# 初始化工序(task)的總數
total_task = 0

# 吃剩下的輸入資料
# 對於屬於每一個job的一組資料去做迭代
for i in range(n_job):
    # 第一行是該job的task總數
    k = int(input())

    # 把該job的task數加到task總數上
    total_task += k

    # 用來裝該job所帶有的task資訊
    tasks = [int(x) for x in input().split()]
    # 再把這些task的資訊拆分裝到job這個list裡面
    for j in range(0, 2 * k, 2):
        job[i].append((tasks[j], tasks[j + 1]))

# 儲存每個machine目前的可使用時間
avl = [0] * n_machine

# 儲存每個job目前執行到的task的完成時間
prev_fin = [0] * n_job

# 儲存目前每個job執行到的task編號
curr_task = [0] * n_job

##### 演算法部分 #####
# 對於每個task去做迭代
# 順序未知，但我們知道總共有total_task個task
# 把完成時間最早的task放進去排程裡
# 若有多個同時完成的task，選擇其job編號最小的task
for _ in range(total_task):
    # 用一個可能的最大值初始化最早(最小)的時間
    earliest_time = float("inf")
    earliest_job = earliest_machine = -1

    # 對每個job去做迭代
    for i in range(n_job):
        if curr_task[i] >= len(job[i]):
            # 如果目前這個job執行到的task編號大於等於該job的task總數
            # 就跳過這次迴圈執行
            continue
        else:
            # 計算對於第i個job的最早完成時間
            # 先拆分目前這個task所需要的machine和該task所需的時間長度
            curr_machine, curr_task_len = job[i][curr_task[i]]
            # 按照題目給的思路找出完成時間
            curr_time = max(avl[curr_machine], prev_fin[i]) + curr_task_len
            if curr_time < earliest_time:
                earliest_time = curr_time
                earliest_job = i
                earliest_machine = curr_machine
    # 更新決定排上去的task的資訊上去
    avl[earliest_machine] = earliest_time
    curr_task[earliest_job] += 1
    prev_fin[earliest_job] = earliest_time

# 印出要求的解答
print(sum(prev_fin))