---
# System prepended metadata

title: Week 8

---

# Week 8

:::info
:::spoiler Click to Open TOC
[TOC]
:::

# Question
:::info
:::spoiler Click to Open Question

## Check
![](https://i.imgur.com/q6BN81s.png)

- [ ] 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)