# Week 8
:::info
:::spoiler Click to Open TOC
[TOC]
:::
# Question
:::info
:::spoiler Click to Open Question
## Check
- [ ] Q1
- [ ] Q2
- [ ] Q3
:::
# Answer
## Q1
> - [name=xian]
:::info
:::spoiler **【題目】**
Show how to use property 2 of Lemma 16.12 to determine in time O(|A|) whether or not a given set A of tasks is independent.
:::
>**【Property 2 of Lemma 16.12】**
> For any set of tasks A
> For $t = 0,1,2,\cdots,n$, we have $N_t(A)\le t$.
> $N_t(A)$ denote the number of tasks in A whose deadline is $t$ or earlier.
**【解題想法】**
1. 建立`N[]`紀錄set A裡每個deadline的個數
2. 從頭計算，將每個`N[i]`和前一個`N[i-1]`加在一起，此時`N[i]`所代表的意思即變為$Lemma\ 16.12裡的N_t(A)$
4. 最後再判斷`N[t]`的大小是否有超過$t$，即$Property\ 2$所給的定義
5. $Lemma16.12$ 的 $n\ 即是|A|的大小，即不會超過|A|的時間$
**【蘇都扣】**
```cpp=
let d[] be the deadline in set A
let all the elements in N[|A|+1] is 0
for i = 1 to |A|:
if d[i] >= |A| //如果A的d[i]超過|A|要放在最後1個
N[|A|]++
else
N[d[i]]++
for t = 1 to |A|:
N[t] = N[t] + N[t-1]
if(N[t] > t) // N_t(A) > t,不符合規定
return false
return true
```
**【時間複雜度】**
根據兩個for迴圈大小 $|A|$，我們可以知道時間複雜度是$O(|A|)_\#$
## Q2
> - [name=Mark]
#### 【解題想法】
題目要求每次都須等到任務一到 n -> 越後面的任務要等越久
先排序，小到大 -> 避免耗時長的任務重覆計算
#### 【Example】
**Normal**
| Task | 1 | 2 | 3 | 4 |
|:-:|:-:|:-:|:-:|:-:|
| $Pi$ | 100 | 4 | 8 | 12 |
$c_{avg}=\frac{[100+(100+4)+(100+4+8)+(100+4+8+12)]}{4}=110$
**Greeedy**
| Task | 2 | 3 | 4 | 1 |
|:-:|:-:|:-:|:-:|:-:|
| $Pi$ | 4 | 8 | 12 | 100 |
$c_{avg}=\frac{[4+(4+8)+(4+8+12)+(4+8+12+100)]}{4}=41$
#### 【蘇都扣】
```cpp=
// S is a set {A1, A2, ...,An} of task
// create c[] to store completion time
// create p[] as MIN-priority queue
MinAvgCompletionTimeScheduling(S)
p[] = MinPriorityQueue(S)
c[1] = p[1]
sum = c[1]
for i = 2 to n
c[i] = c[i - 1] + p[i]
sum += c[i]
return sum / n
```
#### 【Prove】
$p_{i}為個別task所花費時間, \;\; c_{i}為每次執行所費時間$
$\because c_{i}=\sum\limits_{t = 1}^i{p_{t}} \; \; and$
$c_{avg}=\frac{1}{n}\sum\limits_{i = 1}^n{c_{i}}=\frac{1}{n}\sum\limits_{i = 1}^n\sum\limits_{t = 1}^i{p_{t}}=\frac{1}{n}[p_{1}+(p_{1}+p_{2})+(p_{1}+p_{2}+p_{3})+...+(p_{1}+...+p_{n})]$
$\therefore 得出相加的次數從p_{1}到p_{n}遞減 \rightarrow 按p{i}小到大排序可得到最佳解,也就是最小值$
#### 【Time Complexity】
$O(nlgn)$ -> 花在排序
## Q3
> - [name=songchiu]
<!-- **【用到的變數】**
$S[i,t]$ 用來存最佳profit
$time[n]$用來存每個process要花多少時間
$deadline[n]$用來存每個process的deadline是什麼時候
$limit$則是deadline的最大值(最後的deadline) -->
<!-- **【遞迴式】**
$S[i, t] =
\begin{cases}
0 & \mbox{if }i=0\mbox{, t }\leq\mbox{ limit} \\
S[i-1, t] & \mbox{if }min\{t, deadline[i]\}-time[i] < 0 \\
max\{ S[i-1, t], S[i-1, min\{t, deadline[i]\}-time[i]] +1 \} & \mbox{otherwise}
\end{cases}$ -->
**【解題思路】**
1. 透過Moore-Hodgson 演算法來解決此題
2. 將工作以deadline進行排序(ascending)
3. 將工作丟到一個max heap(以執行時間排序)。當總時間>最後一個push進來的job的deadline時，pop heap (把最耗時的那個pop掉)
4. 最大的收益就是heap有幾個元素(因為每個工作的收益都是1)
**【補充說明】**
用執行時間來排序丟到max heap是因為此題的設定每個工作的收益相同，因此我們會希望將執行時間較少的工作留下來
這樣就可以放更多的工作，獲得更多的收入
**【蘇都扣】**
```python=
maxProfit(jobs) {
mergeSort jobs by deadline
time_sum = 0
for j in jobs
push j into max-heap (order by time)
time_sum += j.time
if time_sum > j.deadline
removed_job = pop heap
time_sum -= removed_job.time
heapsort max-heap order by deadline ascending
print heapsort result
}
```
**【時間複雜度】**
MergeSort的$O(n log n)$+把n個工作丟到MaxHeap的$O(n log n)$ + 如果超過deadline，要把heap pop出來的$(n log n)$+heapsort的$O(n log n) = O(n log n)$
**【證明】**
令 $J_i$ 為前面演算法所算出的前$i$個的解，$T_i$ 為$J_i$的processing time總和。
假設在$i = k$時，此敘述正確，我們考慮下列數種$i = k + 1 $的情況：
1. $a_{k+1}$ 排入 $J_k$ 不會超時
$a_{k+1}$ 要排入才可獲得最大的profit，意即 $|J_{k+1}| = |J_k| + 1$，因此 $T_{k+1} = T_k + t_{k+1}$必定為最短
2. $a_{k+1}$ 排入 $J_k$ 會超時且 $t_{k+1} \geq max\{ t_j | 1 ≤ j ≤ k, a_j ∈ J_k \}$
排入 $a_{k+1}$ 只會使$T_{k+1}$更長，而不會使利潤增加，因此$J_{k+1} = J_k$符合敘述
3. $a_{k+1}$ 排入 $J_k$ 會超時且 $t_{k+1} < max\{ t_j | 1 ≤ j ≤ k, a_j ∈ J_k \}$
排入 $a_{k+1}$ 並不會使得profit增加，但可以減少總共的processing time
因此$T_{k+1}$ = $T_k + t_{k+1} - t_j$，其中$t_j$只要選$J_k$當中，最長的即可讓$T_{k+1}$最短
ref: [https://github.com/NCU-CSIE-Algorithmics-A-1061/Homework-7/issues/7](https://github.com/NCU-CSIE-Algorithmics-A-1061/Homework-7/issues/7)
Sign in with Wallet
Connect another wallet