Job Sequencing Problem | Algorithms - Computer Science Engineering (CSE) PDF Download

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.

Examples:
1. Input: Four Jobs with following 

deadlines and profits

Output: Following is maximum
profit sequence of jobs
        c, a

2. Input:  Five Jobs with following
deadlines and profits

Output: Following is maximum
profit sequence of jobs
        c, a, e

A Simple Solution is to generate all subsets of a given set of jobs and check individual subsets for the feasibility of jobs in that subset. Keep track of maximum profit among all feasible subsets. The time complexity of this solution is exponential. 

This is a standard Greedy Algorithm problem.
Following is the algorithm:

1. Sort all jobs in decreasing order of profit.
2. Iterate on jobs in decreasing order of profit.For each job , do the following :

(i) For each job find an empty time slot from deadline to 0. If found empty slot put the job in the slot and mark this slot filled.
The Following is the implementation of the above algorithm.
C++



Java




Python3



Javascript



Output
Following is maximum profit sequence of jobs
c a e

The Time Complexity of the above solution is O(n²). It can be optimized using Disjoint Set Data Structure. Please refer to the below post for details.