This post is completed by 1 user

  • 1
 Add to List
Medium

477. Job Sequencing algorithm

Objective: You are given n jobs along with the deadline and profit for each job. Your task is to write an algorithm to choose the jobs wisely which can maximize the profit. Also compute the maximum profit. Below are the details

  1. Each job duration is 1 unit.
  2. Name - Name of the job.
  3. Deadline - Job should be completed before the deadline is over. For instance if the deadline is 4 then the job has to be completed before 4 time units are over.
  4. Profit - Amount earned if the job has run.

Example:

Jobs	Deadline	Profit
A	2		40
B	1		20
C	4		10
D	1		10

Output: Jobs: B A C, Total Profit: 70


Jobs	Deadline	Profit
A	2		140
B	1		90
C	2		100
D	3		50
E	3		15
Output: Job Sequence: C A D, Total Profit: 290

Approach: Greedy Algorithm

  1. Sort the jobs in descending order of profit. 
  2. Initialize the result, this will store jobs. 
  3. Iterate through all the jobs (from highest profit to lowest), for job j
    1. Pick the job j if this job can be fit into the result without missing the deadline or in other words if current job j does not have any conflict with the jobs already selected in the results.(First job will not have conflict)  then job j to the result. If job j has conflict then ignore this job.
 

Output:

Jobs: C A D , Total Profit: 290

Related Problems: