Weighted Interval Scheduling
===
### 題目
### 解法
定義 OPT(i) 為前 i 個活動可產生的最大權重。
定義 $a_i$ 為第 i 項活動，$w_i$ 為第 i 項活動的權重，$s_i$ 為第 i 項活動的開始時間，$f_i$ 為第 i 項活動的結束時間。
定義 $q_i$ 為排除掉和 $a_i$ 衝突的活動後的最大的 index j 使得 $s_i \ge f_j$，即結束時間最接近 $a_i$ 的活動編號。
1. 將每個活動依照結束時間由小到大排序
2. 計算 $q_i$ for all i
3. 從最後一個活動 $a_i$ 開始排，考慮排入或不排入
Case 1 : 排入活動 $a_i$，需先扣除掉和 $a_i$ 時間衝突的活動，再求出最大的 index j 使得 $s_i \ge f_j$，所以 $OPT(i) = OPT(f(i)) + w_i$
Case 2 : 不排入活動 $a_i$，則 $OPT(i) = OPT(i - 1)$
故 $OPT(i) = \left \{ \begin{array}{rcl} 0 & if\ i = 0 \\
max\{OPT(q_i) + w_i, OPT(i - 1)\} & otherwise\end{array}\right.$
### Time
1. 排序花 O(nlogn)
2. 計算 $q_i$ 可利用 **Binary Search** $\Rightarrow O(nlogn)$
3. 利用 Bottom-up DP 的方式可在 O(n) 內算完 OPT(i) for all i

故整體時間為 O(nlogn)
### 實作

#include <iostream> 
#include <algorithm> 
using namespace std; 

struct Job { 
    int start, finish, weight; 
}; 

bool cmp(Job s1, Job s2) { 
    return s1.finish < s2.finish; 
} 

int binarySearch(Job jobs[], int index) { 
    int low = 0, high = index - 1; // 活動要在 a_i 之前，所以要 index - 1
  
    while (low <= high) { 
        int mid = (low + high) / 2; 
	if (jobs[mid].finish <= jobs[index].start) { 
	    // 這裡有微幅修改 BinarySearch	
            // 先檢查 mid 的下一個有沒有滿足 finish(mid + 1) <= start(index)，
            // 如果沒有滿足，代表 mid 就是我們要找的最大 index，就可以不用繼續二分搜尋了 
            if (jobs[mid + 1].finish <= jobs[index].start) low = mid + 1; 
	    else return mid; 
        } 
	else high = mid - 1; 
    } 

    return -1; // 沒找到，時間都撞到
} 

int findMaxWeight(Job arr[], int n) { 
    sort(arr, arr + n, cmp); 
  
    int *table = new int[n]; 
    table[0] = arr[0].weight; 
 
    for (int i = 1; i < n; i++) { 
	int includeWeight = arr[i].weight, q = binarySearch(arr, i); 
	if (q != -1) includeWeight += table[q]; 
	table[i] = max(includeWeight, table[i-1]); 
    } 

    int result = table[n-1]; 
    delete[] table; 
    return result; 
} 

int main() 
{ 
    Job arr[] = {{3, 10, 20}, {1, 2, 50}, {6, 19, 100}, {2, 100, 200}}; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    cout << "Optimal weight is " << findMaxWeight(arr, n); 
}