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)=\{\begin{array}{rc}0& ifi=0\\ max\{OPT(q_i)+w_i,OPT(i-1)\}& otherwise\end{array}$

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); 
}