Assume we have a set of n
jobs to execute, each of which takes unit time. At any time we can serve exactly one job. Job i
, 1<=i<=n
earns us a profit if and only if it is executed no later than its deadline.
We can a set of jobs feasible if there exists at least one sequence that allows each job in the set to be performed no later than their deadline. "Earliest deadline first" is feasible.
Show that the greedy algorithm is optimal: Add in every step the job with the highest value of profit among those not yet considered, provided that the chosen set of jobs remains feasible.
MUST DO THIS FIRST: show first that is always possible to re-schedule two feasible sequences (one computed by Greedy) in a way that every job common to both sequences is scheduled at the same time. This new sequence might contain gaps.
UPDATE
I created an example that seems to disprove the algorithm:
Assume 4 jobs:
- Job A has profit 1, time duration 2, deadline before day 3;
- Job B has profit 4, time duration 1, deadline before day 4;
- Job C has profit 3, time duration 1, deadline before day 3;
- Job D has profit 2, time duration 1, deadline before day 2.
If we use greedy algorithm with the highest profit first, then we only get job B & C. However, if we do deadline first, then we can get all jobs and the order is CDB
Not sure if I am approaching this question in the right way, since I created an example to disprove what the question wants
In fact, neither "earliest deadline first", "highest profit first" nor "highest profit/duration first" are correct algorithm...
Assume 2 jobs:
Then "earliest deadline first" fails to get correct answer. Correct answer is B.
Assume another 5 jobs:
Then "highest profit first" fails to get correct answer. Correct answer is BCDE.
Assume another 4 jobs:
Then "highest profit/duration first" fails to get correct answer. Correct answer is BC (Thanks for @dognose's counter-example, see comment).
One correct algorithm is Dynamic Programming:
First order by deadline ascending.
dp[i][j] = k
means within the firsti
jobs and withinj
time units we can getk
highest profit. Then initiallydp[0][0] = 0
.Jobs info are stored in 3 arrays: profit are stored in
profit[i], 1<=i<=n
, time duration are stored intime[i], 1<=i<=n
, deadline are stored indeadline[i], 1<=i<=n
.The time/space complexity (which is
n*m
,n
is job count,m
is maximum deadline) of DP algorithm is highly dependent on how many jobs and the maximum deadline. Ifn
and/orm
is rather large, it maybe difficult to get answer, while for common use, it will work well.