Given n Jobs, with their deadline (between 1 to n) and associated profit. Each job takes unit time to complete and you will get the profit only (when the job is completed before the deadline. Sequence the jobs in a way that the profit is maximized.

This problem is one variation of the Activity Selection Problems.

Example1.

Input:
Job: J1, J2, J3, J4
Deadline: 4, 2, 1, 1
Profit: 25, 20, 10, 30

Output: J4, J2, J1 (This is the Sequence of Jobs that will give us max profit).

Example2.

Input:
Job: J1, J2, J3, J4, J5
Deadline: 2, 1, 2, 1, 3
Profit:100, 20, 40, 30, 70

Output: J1, J3, J5 (This is the Sequence of Jobs that will give us max profit = 100+40+70 = 210).
(Note that the sequence can be also. So the order within the sequence is not important as long as the job is finished before the deadline)

Exponential Solution:

Generate all subsets of the given jobs and check individual subset for the feasibility of jobs in that subset (i.e all the jobs in that subset should be do-able before their deadline). Return the maximum profit among all feasible subsets.

The time complexity of this solution is exponential and it is also difficult to implement.

Greedy Solution:

Sort the jobs in decreasing order of their profit. After sorting, the jobs in the second example will look like below:

Job: J1, J5, J3, J4, J2
Deadline: 2, 3, 2, 1, 2
Profit:100, 70, 40, 30, 20

Now iterate over the jobs linearly, and for each job do the following:

Find the maximum timeslot Ti which is empty and is also

Code:

// PROGRAMMING LANGUAGE: C++
void JobScheduling(Job* arr, int n)
{
// Sort the jobs in decreasing order of profit
quickSort(arr); // Need to Implement this function

int result[n]; // FINAL RESULT
bool freeSlot[n]; // TIME SLOTS

// INITIALLY ALL SLOTS ARE FREE
for (int i=0; i=0; j--)
{
if (freeSlot[j])
{
result[j] = i;
freeSlot[j] = false;
break;
}
}
}

// Print the result
for (int i=0; i<< arr[result[i]].id << " ";
}

Time Complexity of this solution is O(n^2).