Horje

INTERVAL scheduling - Applications of Greedy technique - Algorithm
Learn
Algorithm - Applications of Greedy technique - Interval scheduling
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 (opens new window) 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 (opens new window) Shortest interval is not optimal either ce_shortest_intervall.png (opens new window) and fewest conflicts may indeed sound optimal, but here is a problem case for this approach: ce_fewest_conflicts.png (opens new window) 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[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


Read Article
https://develop.horje.com/learn/1434/reference

 

Horje