---
title: Greedy Algorithm / Interval Scheduling
tags: 演算法(交大OCW)
---
# Greedy Algo 介紹
短視近利的一種方法。
將問題拆成很多小步驟，藉由每次選擇該步所看到的「最好」，組成最後的解法
特性是做了決定後不會回頭；可以簡單且快速的想出來。

# 缺點

有可能得出的解法是比較差的。
但不見得每次運氣都這麼差，有可能直接找到最佳解:tea:
所以要證明你採用某種準則的 Greedy 可以找到問題的最佳解

# 常用證法

## 「保持領先」Stays ahead

每次都選擇最好的解，這樣你就是最好的

## 「交換無異」Exchange argument

也是最常用的證明方法

先假設有個人是最佳解，然後我把他跟我的假設中，不同的地方換成我的
>也就是讓他也變成我 Greedy 的形式

發現這麼做並不會讓它變成不是最佳解，這就代表我的也是最佳解

之後會有更詳細的介紹

---

# Interval Scheduling

- Given：你有一堆工作，每個工作都會給你開始跟結束時間
- 在這些工作中，選出一些工作，使得 **「工作數量」** 是最大的

常用在CPU排程，像早期只有單核就很常面臨
假設第 i 個工作，有開始的點 s(i) 跟結束的點 f(i)

$$
s(i),f(i)
$$

f 會是開區間，是為了能夠銜接下一個工作


總之我要選擇能夠工作最多份，不是最長時間，也就是258這三個工作

# Greedy Rule

貪婪演算法說要找到每一步的「最好」，這樣對於每個題目就要定義何謂「最好」
以上面排程的例子來說，制定了一個最好的準則後會篩選出一些工作，然後還要把重疊的給去除掉
然後再從剩下的工作中，再做一次「最好」的準則篩選，然後再去除重複的，直到做完為止。

那這個最好的準則到底是甚麼呢？

此時我們腦力激盪，想到了四種方法：

* 最早開始時間
* 就是每次選工作都選最早開始的做，然後去除掉跟這項工作重疊的
* 最短的時長間距
* 就是每次選工作都選時長最短的做，然後去除掉跟這項工作重疊的
* 最少重疊/衝突
* 就是每次選工作都選跟其他工作衝突最少的做，然後去除掉跟這項工作重疊的
* 最早結束時間
* 就是每次選工作都選最早結束的做，然後去除掉跟這項工作重疊的
*
排程問題的話，最佳解是第四種準則：最早結束時間

:::info
這也是Greedy常令人苦惱的地方，常常最佳的準則都不直覺
:::

那要怎麼證明其他都不行？只要取反例就好

## 最早開始時間

下面是一個工作組合的情形，而在這個情形中，一開始你只能選最下面那個時間很長的工作做
但是這樣你就只能做一個工作，因為其他都被排除掉了。
一開始選擇上面的話可反而可以做四個工作，反例成立。


## 最短的時長間距

一開始選擇下面那個時長最短的做工作，就會排除掉上面兩個工作
但選擇上面的話可以做兩份工作，反例成立


## 最少重疊/衝突

一開始會發現只能選擇深綠色的工作做，因為其他工作都會跟另外其他4個重疊，只有他重疊數是2
但是可以發現，選了深綠色後，最多就只能做 3 份工作，選上面的話反而可以做 4 份，反例成立。


---

# Pseudo Code

在證明前要先給出程式碼，後面證明才能夠敘述

function：Innterval_Scheduling(R)
//R：undetermined requests；A：accepted requests
1. A = {} // empty set
2. while(R is not empty)do
3.    choose a request i in R with minimum f(i) // Greedy rule
4.    A = A + {i}
5.    R = R - {i} - X, where X = {j:j in R and j isn't compatible with i}
6. return A

# 證明
:::success
此處採用的是保持領先，只要證明我一直都是最佳解就好

但是我們不用證明「我就是最好」，我只要說

「我的個數」跟「最好的個數」一樣就好
:::

在此之前需要先證明一個待會會用到的Lemma

## Lemma

我有一個自己用我的演算法所挑的A集合以及最佳集合O；這兩個集合以開始或結束時間排序
至於是選開始或結束時間排序不影響，因為O跟A都是工作不會衝突的集合。

$$
A = \{i_{1}...i_{k}\} \\
O = \{j_{1}...j_{m}\} \\
For\ all\ r\le k,\ f(i_{r})\le f(j_{r})
$$

### Proof 數學歸納法

1. $r=1$ 成立。可以確保兩者是小於等於的關係
2. 如果 $r - 1$ 成立，則

$$
f(i_{r-1})\le f(j_{r-1})\le s(i_{r})
$$

根據 Pseudo code， O的第 r 份工作一定也會被 A 給選到
因此對於 $r$ 也成立

## 證明 反證法

如果我根據我的演算法得到的 A 不是最佳解，代表最佳解 O 有更多的工作數量 Requests
假設 O 有 m 份工作，A 有 k 份工作。根據 Lemma：

$$
For\ all\ r\le k,\ f(i_{r})\le f(j_{r}) \\
f(i_{k})\le f(j_{k}) \le s(j_{k})
$$

根據演算法，O 的第 k+1 個並沒有產生衝突，程式碼會把他加到 A 裡面
但是 A 只有 k 個，代表 A 加入第 k 個工作時， R 就已經空了，矛盾。

所以 m 只能小於等於 k ，代表 A 就是最佳解

# 時間複雜度

## 初始化 R O(nlogn)

1. 將 R 以 f(i) 升序排列，O(nlogn)
還沒講到排序，但是排序最快就是O(nlogn)
這樣 Line 3. 就可以直接獲得最早結束時間的工作
3. 產生一個集合 S = {s(i)}，順序是根據上面 R 的 i
這將會是一個關鍵步驟，待會會說明

## 刪除重疊的工作 O(n)

假如每次都要掃整個 Set ，去找誰跟目前的工作衝突的話，會變成 O(n^2^)
雖然我不是數學家，但是這聽起來不太好，我們希望時間最大就是排序的O(nlogn)

**所以我們得想些巧妙的方法。我們希望只要掃描一次整個 Set 就好**

1. 我選了第 i 個工作。如果第 i + 1 個工作的**開始時間**小於第 i 個工作的**結束時間**
代表會衝突，那我就把他剔除，繼續看向第 i + 2 個，直到第 j 個的**開始時間**，大於第 i 個的**結束時間**。
2. 但如果有個工作，因為結束時間比較大，排在比較後面，同時他的開始時間又小於你現在所選的第 i 個的結束時間；可是你在排除他之前就已經找到一個第 j 個工作，無法排除他。
此時，不用擔心，因為在 i 後面的工作，一定會有一個會將他排除

而要達到「排除下一個的開始時間，大於目前工作的結束時間的工作」的方法，就是前面所建立的 S

:::success
S 可以使用持續增加的 index 變數，或是直接建一個 list
這樣一來，「刪除」這個動作就只要 O(n)
雖然我不是數學家，但這聽起來很不錯對吧
:::

---

# 範例

## 將工作排序好


## 選取第 1 份，排除第 2 份


## 選取第 3 份，排除第 4 份


## 選取第 5 份，排除第 6 份、第 7 份


## 選取第 8 份，排除第 9 份


## 結果 {1,3,5,8}
:::danger
但是要記得，這個演算法目的是找到最大的數量，並給出一種情況
不能給出全部的可能，像是 {2,4,5,8}、{1,4,7,9} 都是可以的組合
:::