Room Scheduling Problem (Interval Graph Coloring)
===
### 題目
### 演算法
定義 min 為在 Interval Graph 上的最小著色數
K 為目前時間點需要至少多少顏色
1. 將活動依開始時間由小到大排序
2. 將活動依結束時間由小到大排序
3. 從最早開始的活動開始上色，直到塗完所有活動
3.1 如果目前的開始時間小於目前最早能結束的活動時間，代表這個活動和其他活動時間上有重疊到，所以要塗上新的顏色才不會撞色。若目前時間點的著色數大於 min 就更新 min。
3.2 如果目前的開始時間大於等於目前最早能結束的活動時間，代表這個活動和其他活動時間上不會衝突，所以目前使用的顏色數可以減少一色。
4. 回傳 min
### Pseudocode
Input : 陣列 start 紀錄每個活動的開始時間、陣列 end 儲存每個活動的結束時間，共 n 個活動
Output : 在 Interval Graph 上的最小著色數

將活動依開始時間由小到大排序
將活動依結束時間由小到大排序

i = 1 // 指向 start 陣列中"正要開始"的活動
j = 0 // 指向 end 陣列中"目前最早結束"的活動
min = 1
K = 1 // 目前有多少活動時間重疊

while (i < n and j < n) {
    // 在 start[i] 時間點，能"最早結束"的活動 j 還在進行中
    // 代表必須為活動 i 塗上新的顏色才不會撞色 (時間衝突)
    if (start[i] < end[j]) {
        K++
        if (K > min) min = colors
        i++ // 活動 i 塗完色了
    } else {
        // 目前活動沒有和其他活動衝突，所以使用的顏色可以減一
        K--
        j++; // 活動 j 結束了
    }
}

return min

### Time O(nlgn)
主要為排序時間，while 的時間為 O(n)
### 正確性證明
在任何時間點，最小著色數(min)一定不會小於最大衝突的數量 (K)，也就是最多有多少活動正在進行。在任意時間點，如果使用了第 K 種顏色，代表第 1 ~ K-1 個顏色都被使用了，也就是至少有 K 個活動時間同時撞到，所以至少需要 K 種顏色，而 K 是最小著色數的下界。