Page 103 - Algorithms Notes for Professionals

// 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.

Below is a Java program that runs in Θ(n log n)

import java.util.Arrays;

colegiohispanomexicano.net – Algorithms Notes 99