# Interval Scheduling

suggest change

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:

1. Earliest start time: Consider jobs in ascending order of `sj`
2. Earliest finish time: Consider jobs in ascending order of `fj`
3. Shortest interval: Consider jobs in ascending order of `fj-sj`
4. Fewest conflicts: For each job `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:

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

// 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;
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 = jobs.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));
}
}```

And the expected output is:

`Optimal profit is 250`

Feedback about page:

Feedback:
Optional: your email if you want me to get back to you:

Table Of Contents