区间调度

我们有一套工作 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