區間排程

我們有一套工作 J={a,b,c,d,e,f,g}。讓 j in J 成為一個工作，而不是從 sj 開始，到 fj 結束。如果兩個作業不重疊，則它們是相容的。以圖片為例： 目標是找到相互相容的作業的最大子集。這個問題有幾種貪婪的方法：

1. 最早的開始時間 ：按照 sj 的升序考慮工作
2. 最早完成時間 ：按照 fj 的升序考慮工作
3. 最短間隔 ：按照 fj-sj 的升序考慮工作
4. 最少的衝突 ：對於每個工作 j，計算相互衝突的工作數量 cj

現在的問題是，哪種方法非常成功。絕對的早期開始時間不是，這裡是一個反例最短的間隔也不是最優的，並且最少的衝突可能確實聽起來是最佳的，但是這種方法存在問題： 這使我們有最早的完成時間。虛擬碼很簡單： **** **** ****

1. 按完成時間排序作業，以便 f1<=f2<=...<=fn
2. 讓 A 成為空集
3. 對於 j=1 到 n 如果 j 與 A set A=A+{j} 中的所有工作相容
4. A 是相互相容的作業的最大子集

或者作為 C++程式：

#include <iostream>
#include <utility>
#include <tuple>
#include <vector>
#include <algorithm>

const int jobCnt = 10;

// Job start times
const int startTimes[] = { 2, 3, 1, 4, 3, 2, 6, 7, 8, 9};

// Job end times
const int endTimes[]   = { 4, 4, 3, 5, 5, 5, 8, 9, 9, 10};

using namespace std;

int main()
{
    vector<pair<int,int>> jobs;
    
    for(int i=0; i<jobCnt; ++i)
        jobs.push_back(make_pair(startTimes[i], endTimes[i]));
    
    // step 1: sort
    sort(jobs.begin(), jobs.end(),[](pair<int,int> p1, pair<int,int> p2) 
                                     { return p1.second < p2.second; });
    
    // step 2: empty set A
    vector<int> A;
    
    // step 3:
    for(int i=0; i<jobCnt; ++i)
    {
        auto job = jobs[i];
        bool isCompatible = true;
        
        for(auto jobIndex : A)
        {
            // test whether the actual job and the job from A are incompatible
            if(job.second >= jobs[jobIndex].first &&
               job.first  <= jobs[jobIndex].second)
            {
                isCompatible = false;
                break;
            }
        }
    
        if(isCompatible)
            A.push_back(i);
    }
    
    //step 4: print A
    cout << "Compatible: ";
    
    for(auto i : A)
        cout << "(" << jobs[i].first << "," << jobs[i].second << ") ";
    cout << endl;
    
    return 0;
}

此示例的輸出為：Compatible: (1,3) (4,5) (6,8) (9,10)

該演算法的實現顯然是Θ（n ^ 2）。有一個Θ（n log n）實現，感興趣的讀者可以繼續閱讀下面的內容（Java 示例）。

現在我們有一個用於區間排程問題的貪心演算法，但它是最優的嗎？

命題： 貪心演算法最早的完成時間是最佳的。

證明:( 矛盾）

假設貪婪不是最優的，i1,i2,...,ik 表示由貪婪選擇的一組工作。讓 j1,j2,...,jm 用最大可能值 i1=j1,i2=j2,...,ir=jr 表示最佳解決方案中的一組作業。 ****

工作 i(r+1) 存在並在 j(r+1)（最早完成）之前完成。但是比 j1,j2,...,jr,i(r+1),j(r+2),...,jm 也是一個最佳的解決方案，並且對於 [1,(r+1)] 中的所有 k 都是 jk=ik。這與 r 的最大化相矛盾。這證明了結論。

第二個例子表明，通常有許多可能的貪婪策略，但只有一些甚至沒有可能在每個例項中找到最佳解決方案。

下面是一個以Θ（n log n）執行的 Java 程式

import java.util.Arrays;
import java.util.Comparator;

class Job
{
    int start, finish, profit;

    Job(int start, int finish, int profit)
    {
        this.start = start;
        this.finish = finish;
        this.profit = profit;
    }
}

class JobComparator implements Comparator<Job>
{
    public int compare(Job a, Job b)
    {
        return a.finish < b.finish ? -1 : a.finish == b.finish ? 0 : 1;
    }
}

public class WeightedIntervalScheduling
{
    static public int binarySearch(Job jobs[], int index)
    {
        int lo = 0, hi = index - 1;

        while (lo <= hi)
        {
            int mid = (lo + hi) / 2;
            if (jobs[mid].finish <= jobs[index].start)
            {
                if (jobs[mid + 1].finish <= jobs[index].start)
                    lo = mid + 1;
                else
                    return mid;
            }
            else
                hi = mid - 1;
        }

        return -1;
    }

    static public int schedule(Job jobs[])
    {
        Arrays.sort(jobs, new JobComparator());

        int n = jobs.length;
        int table[] = new int[n];
        table[0] = jobs[0].profit;

        for (int i=1; i<n; i++)
        {
            int inclProf = jobs[i].profit;
            int l = binarySearch(jobs, i);
            if (l != -1)
                inclProf += table[l];

            table[i] = Math.max(inclProf, table[i-1]);
        }

        return table[n-1];
    }

    public static void main(String[] args)
    {
        Job jobs[] = {new Job(1, 2, 50), new Job(3, 5, 20),
                    new Job(6, 19, 100), new Job(2, 100, 200)};

        System.out.println("Optimal profit is " + schedule(jobs));
    }
}

而預期的產出是：

Optimal profit is 250