Given a list of Jobs with their deadline and profit earned on completion, find the maximum profit earned by executing the Jobs within the specified deadlines.
Assume that each job takes one unit of time to complete, and a job can't run beyond its deadline.
Also, only a single job will be run at a time.
Example 1: Job Sequencing Problem
Input:
| Tasks | Deadlines | Profit |
|---|---|---|
| a | 4 | 20 |
| b | 1 | 10 |
| c | 1 | 40 |
| d | 1 | 30 |
Output: c,a
Example 2: Job Sequencing Problem
Input:
| Tasks | Deadlines | Profit |
|---|---|---|
| a | 2 | 100 |
| b | 1 | 19 |
| c | 2 | 27 |
| d | 1 | 25 |
| e | 3 | 15 |
Output: c,a,e
Solutions
Method 1: Greedy
The greedy algorithm suggest to Iterate on jobs in decreasing order of profit and for each job find a time slot "T", such that slot is empty and T < deadline and T is greatest.
1) Sort all jobs in decreasing order of profit.
2) Iterate on jobs and for each job find a time slot "T", such that slot is empty and T < Deadline and T is greatest.
3) If slot is empty, put the job in his slot and mark this slot filled, else if no such slot - "T" exists, then ignore the job.