Page 102 - Algorithms Notes for Professionals

Shortest interval is not optimal either

and fewest conflicts may indeed sound optimal, but here is a problem case for this approach:

Which leaves us with earliest finish time. The pseudo code is quiet simple:

1. Sort jobs by finish time so that f1<=f2<=...<=fn
2. Let A be an empty set
3. for j=1 to n if j is compatible to all jobs in A set A=A+{j}
4. A is a maximum subset of mutually compatible jobs

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

colegiohispanomexicano.net – Algorithms Notes 98