# Interval Scheduling

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:

**Earliest start time**: Consider jobs in ascending order of`sj`

**Earliest finish time**: Consider jobs in ascending order of`fj`

**Shortest interval**: Consider jobs in ascending order of`fj-sj`

**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:

- Sort jobs by finish time so that
`f1<=f2<=...<=fn`

- Let
`A`

be an empty set - for
`j=1`

to`n`

if`j`

is compatible to**all**jobs in`A`

set`A=A+{j}`

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

And the expected output is:

Optimal profit is 250