Resource Scheduler - Greedy Algorithm
As a project for CS504, we are to analyze an algorithm and post a javascript version of it, which verifies the run time analysis. The algorithm to which I was assigned is a resource scheduler using a greedy algorithm.
Suppose we have a set of activities A = {1, 2, 3, ..., n}
Each activity i, has a beginning and ending time, bi and ei
We will try to build up the set of scheduled activities S.
To improve the running time of the algorithm we do some pre-processing, that is, we sort A by the start time of the activity.
The algorithm itself :
int n = sizeof(A)
S = {1}
int j = 1
for (i = 2 to n) do
if (Ai >= ej) then
S = S U {i}
j = i
endif
return S;
Enter the starting and stopping times in the box below.
A value of 1, 10, 5, 15, 20, 40 would define 3 events, the first event will begin at time 1 and goto time 10, the second event will begin at time 5 and go to time 15, and the third event will begin at time 20 and go to time 40.
The analysis
This algorithm assumes that the data need be sorted. We will assume this will take n lg n time to complete.
Once sorted the algorithm will make a schedule using a greedy algorithm. That is it does not try to schedule the most activities, nor does it prioritize the activities, but rather it schedules first come first serve.
The algorithm will make one comparison per data element minus one as part of the for loop to look at all the elements. Each element will then be assessed to see if it can be scheduled. Elements which can
be scheduled will be copied into the final schedule set.
If we assume that any given activity has a 50% chance of being able to be scheduled, then the cost for this algorithm is 2*(n-1) + n/2 = (5n + 4)/2
This be because we make 2 comparisons for elements 2..n(one for indexing and one for determination of inclusion). We then take 50% of the elements and copy them into the final schedule.
Therefore the total time for this algorithm, including sort time, is n lg n + (5n + 4)/2
References
David Flanagan - Javascript, the definitive guide. (3rd ed)
Corme, Leiserson, Rivest - Introduction to Algorithms