Job Sequencing with given deadline

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 <J3, J1, J5> 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 <= deadline of the current job. If no such timeslot exist, ignore the current job.

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<n; i++) 
      freeSlot[i] = true; 

   for (int i=0; i<n; i++) 
   { 
      for (int j=min(n, arr[i].deadline)-1; j>=0; j--) 
      { 
         if (freeSlot[j]) 
         { 
            result[j] = i; 
            freeSlot[j] = false; 
            break; 
         } 
      } 
   } 

   // Print the result 
   for (int i=0; i<n; i++) 
      if (freeSlot[i]) 
        cout << arr[result[i]].id << " "; 
} 

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