Job Scheduling Problem using Greedy Approach

Problem statement: Given an array of jobs where every job has a deadline and associated profit if the job is finished before the deadline. It is also given that every job takes a single unit of time, so the minimum possible deadline for any job is 1. How to maximize total profit if only one job can be scheduled at a time.

Let’s break the question and try to find an approach for the same

• Given: array of jobs, array of deadline, array of profit
• Each job takes a unit time to complete
• A job can be completed on or before its deadline
• With every job completion, a profit will be earned
• We are asked to maximize the profit — which means it’s an optimization problem.

For optimization problems like this we generally use the GREEDY approach.

Here in this question we need to pick the best slot for a job to finish itself on or before it’s deadline.

According to GREEDY, we need to pick the job that will have greater profit

Total Profit: 20+30+40 = 90

If we arrange the given arrays according to the decreasing profit, it’ll get easier for us to pick the jobs.

Now, let’s go ahead with the solution:

Algorithm for the problem is as follows:

Therefore the final output/result will be-

RESULT = 100+60+50 =210