Event Scheduling problem : Greedy algorithm

Event scheduling problem

Any event has two time stamps, start timestamp and end timestamp. When number of events have to be scheduled on to particular resource, we need to take care that no two events are no overlapping, that is to say second event cannot be scheduled while first running. Given a set of jobs S with their start time and end time, find out largest set R such that all events in R are mutually compatible. Two events are compatible if they do not overlap. This problem is known as event scheduling problem.

First information we got from problem statement is that its about maximizing the output with a given constraint. Great! What template this problem fit in? There are two approaches in we can apply : Dynamic programming or greedy algorithm. Let’s start with greedy algorithm and see if it gives optimal answer in all the cases, if not then we will look into dynamic programming approach.

We need to select each job which maximizes output, i.e gives us maximum number of compatible jobs. What should be the selection criteria for the job? There are three criteria we can think of :
1. We take job with earliest start time first.
2. We take job with earliest end time first.
3. We take job with minimum number of overlapping jobs.
4. We take the shortest job first.

Let’s take some examples and see how things work out with each criteria.
1. Earliest  start time first
event scheduling problem

2. Minimum number of conflicting jobs
event scheduling example3. Shortest job first.

event scheduling problem implementation
So we get from above figures that these three criteria cannot give us optimum output. If we take job with earliest finish time, we can find out the optimal set.

1. Take the job which has earliest finish time.
2. Now eliminate all events which have start time less than selected job's end time.
3. Add first event to which has start time greater than selected end time set.
4. Repeat Step 2 and 3 till we have considered all jobs.

Sort all jobs which based on end time and then go for the above algorithm.

Event scheduling problem : greedy algorithm implementation

#include <stdio.h>
 
typedef struct job{
    int startTime;
    int endTime;
    int jobNum;
}job;
 
void swap(job jobs[], int i, int j){
    int tempStart = jobs[i].startTime;
    int tempEnd = jobs[i].endTime;
    int jobNum = jobs[i].jobNum;
 
    jobs[i].startTime  = jobs[j].startTime ;
    jobs[i].endTime  = jobs[j].endTime ;
    jobs[i].jobNum  = jobs[j].jobNum;
 
    jobs[j].startTime  = tempStart;
    jobs[j].endTime  = tempEnd ;
    jobs[j].jobNum  = jobNum;
}
 
int partition(job jobs[], int start, int njobs){
    int i,j;
 
    int pivot =  jobs[start].endTime;
    i = start+1;
    j = njobs;
 
    while(i<=j){
        while(i<=njobs && jobs[i].endTime < pivot)
            i++;
        while(j>start && jobs[j].endTime >= pivot)
            j--;
        if(i<j){
            swap(jobs, i, j);
        }
    }
    if(j>start)
        swap(jobs,start, j);
    return j;
}
 
/* Simple Implementation of quick sort */
void quickSort(job jobs[], int start, int njobs){
 
    if(start >=njobs) return;
    int pivot = partition(jobs, start, njobs);
 
    quickSort(jobs, start, pivot);
    quickSort(jobs, pivot+1, njobs);
}
 
 
void maxCompatibleJobs(job jobs[], int njobs){
 
   int startTime[njobs];
 
   int count = 0;
   int i, currentJob;
   int jobSequence[njobs];
 
   /* Do sorting on end time */
   quickSort(jobs, 0, njobs-1);
 
   /* Start with the job with least end time */
   jobSequence[0] = jobs[0].jobNum;
   currentJob =0;
 
    while(currentJob < njobs){
       i = 0;
        /* While we find a job with start time greater than current
        end time, go forward */
        while(i<njobs && 
            jobs[i].startTime < jobs[currentJob].endTime){
            i++;
        }
        if(i<njobs)
           jobSequence[++count] = jobs[i].jobNum;
 
        currentJob = i ;
    }
    printf("\n Compatible jobs :");
    for(i=0; i<=count; i++){
        printf("%d ", jobSequence[i]);
    }
}
 
//Driver program
int main(){
 
    job jobs[5];
 
    jobs[0].startTime = 0;
    jobs[0].endTime = 2;
    jobs[0].jobNum = 1;
 
    jobs[1].startTime = 2; 
    jobs[1].endTime = 3;
    jobs[1].jobNum = 2;
 
    jobs[2].startTime = 1;
    jobs[2].endTime = 5;
    jobs[2].jobNum = 3;
 
    jobs[3].startTime = 3;
    jobs[3].endTime = 7;
    jobs[3].jobNum = 4;
 
    jobs[4].startTime = 8;
    jobs[4].endTime = 9;
    jobs[4].jobNum = 5;
 
    maxCompatibleJobs(jobs, 5);
 
    return 0;
}

Complexity of algorithm to solve event scheduling problem is dominated by the sorting which is O(N log N).
Reference
http://courses.cs.vt.edu/cs5114/spring2009/lectures/lecture04-greedy-scheduling.pdf

Please share if there is something wrong or missing. If you are interested in contributing to algorithmsandme, please contact us.