We have a set of jobs J={a,b,c,d,e,f,g}
. Let j in J
be a job than its start at sj
and ends at fj
. Two jobs are compatible if they don’t overlap. A picture as example: intervall_scheduling.png The goal is to find the maximum subset of mutually compatible jobs. There are several greedy approaches for this problem:
sj
fj
fj-sj
j
, count the number of conflicting jobs cj
The question now is, which approach is really successfull. Early start time definetly not, here is a counter example ce_early.png Shortest interval is not optimal either ce_shortest_intervall.png and fewest conflicts may indeed sound optimal, but here is a problem case for this approach: ce_fewest_conflicts.png Which leaves us with earliest finish time. The pseudo code is quiet simple:
f1<=f2<=...<=fn
A
be an empty setj=1
to n
if j
is compatible to all jobs in A
set A=A+{j}
A
is a maximum subset of mutually compatible jobsOr as C++ program:
#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;
}
The output for this example is: Compatible: (1,3) (4,5) (6,8) (9,10)
The implementation of the algorithm is clearly in Θ(n^2). There is a Θ(n log n) implementation and the interested reader may continue reading below (Java Example).
Now we have a greedy algorithm for the interval scheduling problem, but is it optimal?
Proposition: The greedy algorithm earliest finish time is optimal.
Proof:(by contradiction)
Assume greedy is not optimal and i1,i2,...,ik
denote the set of jobs selected by greedy. Let j1,j2,...,jm
denote the set of jobs in an optimal solution with i1=j1,i2=j2,...,ir=jr
for the largest possible value of r
.
The job i(r+1)
exists and finishes before j(r+1)
(earliest finish). But than is j1,j2,...,jr,i(r+1),j(r+2),...,jm
also a optimal solution and for all k
in [1,(r+1)]
is jk=ik
. thats a contradiction to the maximality of r
. This concludes the proof.
This second example demonstrates that there are usually many possible greedy strategies but only some or even none might find the optimal solution in every instance.