Job Sequencing Problem (Greedy algorithm)

Posted by on Mar 31, 2024

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.

Complexity
The Time Complexity of the above solution is O(n2).

Related


Fractional Knapsack Problem (Greedy Approach)

Activity Selection Problem (Greedy algorithm)