Job Scheduling
In this page:
Problem Idea
Job sequencing with deadlines gives each job both a deadline and a profit, and the goal is to choose which jobs to actually run (each job takes one unit of time, and only one job can run per unit of time) to maximize total profit earned.
Example: Problem Idea
#include <iostream>
using namespace std;
int main() {
int deadlines[] = {2,1,2,1,3}, profits[] = {100,19,27,25,15};
cout << "Choose jobs to maximize profit, each takes 1 unit of time, only one job per time slot";
return 0;
}public class Main {
public static void main(String[] args) {
int[] deadlines = {2,1,2,1,3}, profits = {100,19,27,25,15};
System.out.println("Choose jobs to maximize profit, each takes 1 unit of time, only one job per time slot");
}
}deadlines, profits = [2,1,2,1,3], [100,19,27,25,15]
print("Choose jobs to maximize profit, each takes 1 unit of time, only one job per time slot")#include <stdio.h>
int main() {
int deadlines[] = {2,1,2,1,3}, profits[] = {100,19,27,25,15};
printf("Choose jobs to maximize profit, each takes 1 unit of time, only one job per time slot");
return 0;
}Login to try C/C++/Java code in the editor
Sort by Profit
The safe greedy order here is by profit, from highest to lowest — considering the most valuable jobs first gives them the best chance of finding an available time slot before their deadline passes.
Example: Sort by Profit
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<pair<int,int>> jobs = {{2,100},{1,19},{2,27},{1,25},{3,15}};
sort(jobs.begin(), jobs.end(), [](auto&a, auto&b){ return a.second > b.second; });
cout << "Highest profit job first: deadline=" << jobs[0].first << " profit=" << jobs[0].second;
return 0;
}import java.util.*;
public class Main {
public static void main(String[] args) {
int[][] jobs = {{2,100},{1,19},{2,27},{1,25},{3,15}};
Arrays.sort(jobs, (a,b) -> b[1]-a[1]);
System.out.println("Highest profit job first: deadline=" + jobs[0][0] + " profit=" + jobs[0][1]);
}
}jobs = [(2,100),(1,19),(2,27),(1,25),(3,15)]
jobs.sort(key=lambda j: -j[1])
print(f"Highest profit job first: deadline={jobs[0][0]} profit={jobs[0][1]}")#include <stdio.h>
int main() {
int jobs[5][2] = {{2,100},{1,19},{2,27},{1,25},{3,15}};
for (int i = 0; i < 5; i++)
for (int j = i+1; j < 5; j++)
if (jobs[j][1] > jobs[i][1]) { int t0=jobs[i][0],t1=jobs[i][1]; jobs[i][0]=jobs[j][0]; jobs[i][1]=jobs[j][1]; jobs[j][0]=t0; jobs[j][1]=t1; }
printf("Highest profit job first: deadline=%d profit=%d", jobs[0][0], jobs[0][1]);
return 0;
}Login to try C/C++/Java code in the editor
Find a Slot
For each job in that order, the algorithm looks for the latest available time slot that is still at or before that job's deadline; scheduling as late as possible, rather than as early as possible, is the trick that makes this greedy approach work.
Example: Find a Slot
#include <iostream>
using namespace std;
int main() {
int slots[4] = {0,0,0,0};
int deadline = 2, jobId = 7;
for (int t = deadline; t >= 1; t--)
if (slots[t] == 0) { slots[t] = jobId; cout << "Placed job " << jobId << " at slot " << t; break; }
return 0;
}public class Main {
public static void main(String[] args) {
int[] slots = new int[4];
int deadline = 2, jobId = 7;
for (int t = deadline; t >= 1; t--)
if (slots[t] == 0) { slots[t] = jobId; System.out.println("Placed job " + jobId + " at slot " + t); break; }
}
}slots = [0]*4
deadline, job_id = 2, 7
for t in range(deadline, 0, -1):
if slots[t] == 0:
slots[t] = job_id
print(f"Placed job {job_id} at slot {t}")
break#include <stdio.h>
int main() {
int slots[4] = {0,0,0,0};
int deadline = 2, jobId = 7;
for (int t = deadline; t >= 1; t--)
if (slots[t] == 0) { slots[t] = jobId; printf("Placed job %d at slot %d", jobId, t); break; }
return 0;
}Login to try C/C++/Java code in the editor
Maximize Profit
Filling the latest available slot instead of the earliest leaves the earlier, more constrained slots open for jobs with earlier deadlines that come later in the profit-sorted order — an earlier slot used up too soon can strand a tight-deadline job with nowhere to go.
Example: Maximize Profit
#include <iostream>
using namespace std;
int main() {
cout << "Filling latest slot first leaves earlier, tighter slots open for later, earlier-deadline jobs";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Filling latest slot first leaves earlier, tighter slots open for later, earlier-deadline jobs");
}
}print("Filling latest slot first leaves earlier, tighter slots open for later, earlier-deadline jobs")#include <stdio.h>
int main() {
printf("Filling latest slot first leaves earlier, tighter slots open for later, earlier-deadline jobs");
return 0;
}Login to try C/C++/Java code in the editor
Practice
Try a handful of jobs with mixed deadlines and profits: sort by profit, then place each into the latest still-open slot at or before its deadline, and see how the total profit compares to a naive earliest-slot approach.
Example: Practice
#include <iostream>
using namespace std;
int main() {
cout << "Sort by profit, place each job in the latest still-open slot at or before its deadline";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Sort by profit, place each job in the latest still-open slot at or before its deadline");
}
}print("Sort by profit, place each job in the latest still-open slot at or before its deadline")#include <stdio.h>
int main() {
printf("Sort by profit, place each job in the latest still-open slot at or before its deadline");
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 5 topics to unlock
0/5 topics done
Complete these topics first: