Problem Statement
Given an array of jobs having a specific deadline and associated with a profit, provided the job is completed within the given deadline. The task is to maximize the profit by arranging the jobs in a schedule, such that only one job can be done at a time.
Examples:
Input:
Output: J4 J3 J1 J2
Explanation:
Total profit – 20 + 25 + 35 + 30 = 110
Approach 1: Greedy Algorithm
Since, the task is to get the maximum profit by scheduling the jobs, the idea is to approach this problem greedily.
Algorithm
- Sort the jobs based on decreasing order of profit.
- Iterate through the jobs and perform the following:
- Choose a Slot i if:
- Slot i isn’t previously selected.
- I < deadline
- I is maximum
- If no such slot exists, ignore the job and continue.
- Choose a Slot i if:
Dry Run with Example
Given Jobs:
Sort in decreasing order of profits:
C++ Implementation
struct Job
{
char id;
int dead;
int profit;
};
bool comparison(Job a, Job b)
{
return (a.profit > b.profit);
}
void printJobScheduling(Job arr[], int n)
{
sort(arr, arr+n, comparison);
int result[n];
bool slot[n];
for (int i=0; i<n; i++)
slot[i] = false;
for (int i=0; i<n; i++)
{
for (int j=min(n, arr[i].dead)-1; j>=0; j--)
{
if (slot[j]==false)
{
result[j] = i;
slot[j] = true;
break;
}
}
}
for (int i=0; i<n; i++)
if (slot[i])
cout << arr[result[i]].id << " ";
}
Java Implementation
class Job
{
char id;
int deadline, profit;
public Job() {}
public Job(char id, int deadline, int profit)
{
this.id = id;
this.deadline = deadline;
this.profit = profit;
}
void printJobScheduling(ArrayList<Job> arr, int t)
{
int n = arr.size();
Collections.sort(arr,
(a, b) -> b.profit - a.profit);
boolean result[] = new boolean[t];
char job[] = new char[t];
for (int i = 0; i < n; i++)
{
for (int j
= Math.min(t - 1, arr.get(i).deadline - 1);
j >= 0; j--) {
if (result[j] == false)
{
result[j] = true;
job[j] = arr.get(i).id;
break;
}
}
}
for (char jb : job)
{
System.out.print(jb + " ");
}
System.out.println();
}
Python Implementation
def printJobScheduling(arr, t):
n = len(arr)
for i in range(n):
for j in range(n - 1 - i):
if arr[j][2] < arr[j + 1][2]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
result = [False] * t
job = ['-1'] * t
for i in range(len(arr)):
for j in range(min(t - 1, arr[i][1] - 1), -1, -1):
if result[j] is False:
result[j] = True
job[j] = arr[i][0]
break
print(job)
Time Complexity: O(N^2), where N is the size of the jobs array
Space Complexity: O(1), since no extra space is used.
Efficient Approach: Using Set
In the previous approach, for each job, we had to iterate through all other jobs and find a job satisfying the given conditions. But the time complexity is O(N^2) in the worst case. It can be improved further using sets.
The idea is to apply binary search on the set and find the jobs satisfying the given conditions
Algorithm:
- Sort the jobs based on decreasing order of profit.
- Create two variables, total_jobs = 0, maxprofit = 0.
- Also, find the maximum deadline among all the jobs.
- Initialise a set storing all the jobs in decreasing order.
- Iterate through the jobs and perform the following:
- If the set is empty or the deadline of the current job is less than the last element of the set, ignore the job.
- Else, apply binary search and find the nearest Slot i, such that i < deadline and add the profit.
- Increment total jobs by 1 and remove the ith element from the set.
- Return the maximum profit.
C++ Implementation of Approach
bool compare(vector<int> &job1, vector<int> &job2)
{
return job1[1] > job2[1];
}
int jobScheduling(vector<vector<int>> &jobs)
{
sort(jobs.begin(), jobs.end(), compare);
int maxProfit = 0;
int maxDeadline = 0;
for (int i = 0; i < jobs.size(); i++)
{
maxDeadline = max(maxDeadline, jobs[i][0]);
}
set<int, greater<int>> slots;
for (int i = maxDeadline; i > 0; i--)
{
slots.insert(i);
}
for (int i = 0; i < jobs.size(); i++)
{
if (slots.size() == 0 || jobs[i][0] < *slots.rbegin())
{
continue;
}
int availableSlot = *slots.lower_bound(jobs[i][0]);
maxProfit = maxProfit + jobs[i][1];
slots.erase(availableSlot);
}
return maxProfit;
}
Java Implementation of Approach
public static int jobScheduling(int[][] jobs)
{
Arrays.sort(jobs, new Comparator<int[]>(){
public int compare(int[] first, int[] second)
{
if(first[1] < second[1]) return 1;
else return -1;
}
});
int maxProfit = 0;
int maxDeadline = 0;
for (int i = 0; i < jobs.length; i++)
{
maxDeadline = Math.max(maxDeadline, jobs[i][0]);
}
TreeSet<Integer> set = new TreeSet<Integer>();
for (int i = maxDeadline; i > 0; i--)
{
set.add(i);
}
TreeSet<Integer> slots = (TreeSet<Integer>)set.descendingSet();
for (int i = 0; i < jobs.length; i++)
{
if (slots.size() == 0 || jobs[i][0] < slots.last())
{
continue;
}
Integer availableSlot = -1;
for (Integer val : slots)
{
if (val <= jobs[i][0])
{
availableSlot = val;
break;
}
}
if (availableSlot != -1)
{
maxProfit = maxProfit + jobs[i][1];
slots.remove(availableSlot);
}
}
return maxProfit;
}
Python Implementation of Approach
import bisect
def jobScheduling(jobs):
jobs.sort(key = lambda x: (-x[1], -x[0]))
maxProfit = 0
maxDeadline = 0
for i in range(0, len(jobs)):
maxDeadline = max(maxDeadline, jobs[i][0])
slots = list()
for i in range(1, maxDeadline + 1):
slots.append(i)
maxProfit = 0
for i in range(len(jobs)):
if len(slots) == 0 or jobs[i][0] < slots[0]:
continue
availableSlot = slots[bisect.bisect(slots, jobs[i][0]) - 1]
maxProfit += jobs[i][1]
slots.remove(availableSlot)
return maxProfit
Time Complexity: O(NlogN), where N is the size of the jobs array
Space Complexity: O(max(deadline)), since set is used.
FAQs
Q. Do we need to sort the jobs array?
Yes, we need to sort the jobs array according to profit. Else, all the possible subsets need to be found, which would lead to an exponential solution.
Q. What is the most efficient algorithm to solve the Job Sequencing problem?
The job sequencing problem can be solved using the binary search approach using sets. The idea is to find the job corresponding to an ith job whose deadline is less than the current job. This leads to an O(NlogN) approach.
