# Job Sequencing Problem with Deadlines

Given a set of tasks with deadlines and total profit earned on completion of a task, find maximum profit earned by executing the tasks within the specified deadlines. Assume any task will take one unit of time to execute and any task can’t execute beyond its deadline. Also, only one task can be executed at a time.

For example, consider below set of tasks that have a deadline and profit associated with it. If we choose tasks 1, 3, 4, 5, 6, 7, 8 and 9, we can achieve maximum profit of 109. Note that task 2 and task 10 are left out.

 Tasks Deadlines Profit 1 9 15 2 2 2 3 5 18 4 7 1 5 4 25 6 2 20 7 5 8 8 7 10 9 4 12 10 3 5

We can easily solve this problem by following a Greedy approach. The idea is very simple. We consider each task in decreasing order of their profits and schedule it in the latest possible free slot that meets its deadline. If no such slot is there, don’t schedule the task.

Below table shows the tasks arranged based on their associated profits. Here task 5 has maximum priority associated with it as it has maximum profit of 30. Similarly, task 4 has least priority. Greedy approach will consider the tasks in decreasing order of their priority.

 Tasks Deadlines Profit (Maximum first) 5 4 25 6 2 20 3 5 18 1 9 15 9 4 12 8 7 10 7 5 8 10 3 5 2 2 2 4 7 1

To demonstrate the greedy approach, lets consider the deadlines in form of circular structure as shown below. Each slot can be filled by a given task. Now lets start allocated the tasks based on the deadlines. We will start with task 5 having deadline 4 and fill it empty slot 3-4.

Next consider task 6 having deadline 2 and fill it empty slot 1-2.

Next consider task 3 having deadline 5 and fill it empty slot 4-5.

Next consider task 1 having deadline 9 and fill it empty slot 8-9.

Next consider task 9 having deadline 4. As slot 3-4 is already filled with task 5, we will consider next free slot 2-3 and assign task 9 to it.

Next consider task 8 having deadline 7 and fill it empty slot 6-7.

Next consider task 7 having deadline 5. As slot 4-5 is already filled with task 3, we will consider next free slot 0-1 and assign task 7 to it.

Below is C++ and Java implementation of Job sequencing problem:

## C++

Output:

The Scheduled jobs are – 7 6 9 5 3 4 8 1
Total Profit is 109

## Java

Output:

The Scheduled jobs are –
7
6
9
5
3
4
8
1

Total Profit is: 109

Time complexity of above solution is O(n2).

References:

(2 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Subscribe
Notify of
Guest

Good post!!

Guest
Tanmay Jha

Nice greedy algorithm.

Guest

Could you explain why do we put any task with max profit only at the latest possible slot and not anywhere else? I understand it intuitively but I’m not able to frame an explanation

Guest

It’s greedy algorithm..