Problem Statement: You are given a set of N jobs where each job comes with a deadline and profit. The profit can only be earned upon completing the job within its deadline. Find the number of jobs done and the maximum profit that can be obtained. Each job takes a single unit of time and only one job can be performed at a time.
Examples
Example 1:
Input: N = 4, Jobs = {(1,4,20),(2,1,10),(3,1,40),(4,1,30)}
Output: 2 60
Explanation: The 3rd job with a deadline 1 is performed during the first unit of time .The 1st job is performed during the second unit of time as its deadline is 4.
Profit = 40 + 20 = 60
Example 2:
Input: N = 5, Jobs = {(1,2,100),(2,1,19),(3,2,27),(4,1,25),(5,1,15)}
Output: 2 127
Explanation: The first and third job both having a deadline 2 give the highest profit.
Profit = 100 + 27 = 127
Solution
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Approach: The strategy to maximize profit should be to pick up jobs that offer higher profits. Hence we should sort the jobs in descending order of profit. Now say if a job has a deadline of 4 we can perform it anytime between day 1-4, but it is preferable to perform the job on its last day. This leaves enough empty slots on the previous days to perform other jobs.
Basic Outline of the approach:-
- Sort the jobs in descending order of profit.
- If the maximum deadline is x, make an array of size x .Each array index is set to -1 initially as no jobs have been performed yet.
- For every job check if it can be performed on its last day.
- If possible mark that index with the job id and add the profit to our answer.
- If not possible, loop through the previous indexes until an empty slot is found.
DRY RUN:
Profit = 90 , No of jobs done = 3
Code:
C++ Code
#include<bits/stdc++.h>
using namespace std;
// A structure to represent a job
struct Job {
int id; // Job Id
int dead; // Deadline of job
int profit; // Profit if job is over before or on deadline
};
class Solution {
public:
bool static comparison(Job a, Job b) {
return (a.profit > b.profit);
}
//Function to find the maximum profit and the number of jobs done
pair < int, int > JobScheduling(Job arr[], int n) {
sort(arr, arr + n, comparison);
int maxi = arr[0].dead;
for (int i = 1; i < n; i++) {
maxi = max(maxi, arr[i].dead);
}
int slot[maxi + 1];
for (int i = 0; i <= maxi; i++)
slot[i] = -1;
int countJobs = 0, jobProfit = 0;
for (int i = 0; i < n; i++) {
for (int j = arr[i].dead; j > 0; j--) {
if (slot[j] == -1) {
slot[j] = i;
countJobs++;
jobProfit += arr[i].profit;
break;
}
}
}
return make_pair(countJobs, jobProfit);
}
};
int main() {
int n = 4;
Job arr[n] = {{1,4,20},{2,1,10},{3,2,40},{4,2,30}};
Solution ob;
//function call
pair < int, int > ans = ob.JobScheduling(arr, n);
cout << ans.first << " " << ans.second << endl;
return 0;
}
Output: 3 90
Time Complexity: O(N log N) + O(N*M).
O(N log N ) for sorting the jobs in decreasing order of profit. O(N*M) since we are iterating through all N jobs and for every job we are checking from the last deadline, say M deadlines in the worst case.
Space Complexity: O(M) for an array that keeps track on which day which job is performed if M is the maximum deadline available.
Java Code
import java.io.*;
import java.lang.*;
import java.util.*;
class Job {
int id, profit, deadline;
Job(int x, int y, int z) {
this.id = x;
this.deadline = y;
this.profit = z;
}
}
class solve {
// return an array of size 2 having the 0th element equal to the count
// and 1st element equal to the maximum profit
int[] JobScheduling(Job arr[], int n) {
Arrays.sort(arr, (a, b) -> (b.profit - a.profit));
int maxi = 0;
for (int i = 0; i < n; i++) {
if (arr[i].deadline > maxi) {
maxi = arr[i].deadline;
}
}
int result[] = new int[maxi + 1];
for (int i = 1; i <= maxi; i++) {
result[i] = -1;
}
int countJobs = 0, jobProfit = 0;
for (int i = 0; i < n; i++) {
for (int j = arr[i].deadline; j > 0; j--) {
// Free slot found
if (result[j] == -1) {
result[j] = i;
countJobs++;
jobProfit += arr[i].profit;
break;
}
}
}
int ans[] = new int[2];
ans[0] = countJobs;
ans[1] = jobProfit;
return ans;
}
}
class Main {
public static void main(String[] args) throws IOException {
//size of array
Job[] arr = new Job[4];
arr[0] = new Job(1, 4, 20);
arr[1] = new Job(2, 1, 10);
arr[2] = new Job(3, 2, 40);
arr[3] = new Job(4, 2, 30);
solve ob = new solve();
//function call
int[] res = ob.JobScheduling(arr, 4);
System.out.println(res[0] + " " + res[1]);
}
}
Output: 3 90
Time Complexity: O(N log N) + O(N*M).
O(N log N ) for sorting the jobs in decreasing order of profit. O(N*M) since we are iterating through all N jobs and for every job we are checking from the last deadline, say M deadlines in the worst case.
Space Complexity: O(M) for an array that keeps track of which day job is performed if M is the maximum deadline available.
Python Code
class job:
def __init__(self, id, deadline, profit):
self.id = id
self.deadline = deadline
self.profit = profit
class Solution:
def jobScheduling(self, jobs):
jobs.sort(key=lambda x: x.profit, reverse=True)
maxi = jobs[0].deadline
for i in range(1, len(jobs)):
maxi = max(maxi, jobs[i].deadline)
slot = [-1] * (maxi + 1)
countJobs = 0
jobProfit = 0
for i in range(len(jobs)):
for j in range(jobs[i].deadline, 0, -1):
if slot[j] == -1:
slot[j] = i
countJobs += 1
jobProfit += jobs[i].profit
break
return countJobs, jobProfit
if __name__ == "__main__":
jobs = [job(1, 4, 20), job(2, 1, 10), job(3, 2, 40), job(4, 2, 30)]
count, profit = Solution().jobScheduling(jobs)
print(count, profit)Output: 3 90
Time Complexity: O(N log N) + O(N*M).
O(N log N ) for sorting the jobs in decreasing order of profit. O(N*M) since we are iterating through all N jobs and for every job we are checking from the last deadline, say M deadlines in the worst case.
Space Complexity: O(M) for an array that keeps track of which day job is performed if M is the maximum deadline available.
Special thanks to Somparna Chakrabarti and Sudip Ghosh for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article