Scheduling with Deadlines
Editorial
One job a day
Each job takes one day, and you can do one job a day. A job pays only if it's done on or before its deadline. Which jobs, on which days, earn the most? The greedy way takes the most profitable job first and gives it a day, but which day: the first free one, or the last free one before the deadline? Both rules against trying every set of jobs, on every job set of up to 4 jobs, and on seven jobs this lesson comes back to:
from itertools import permutations, product
def best(deadline, profit): # every set of jobs: does it fit, and what does it earn?
n, top = len(deadline), 0
for mask in range(1 << n):
days = sorted(deadline[i] for i in range(n) if mask >> i & 1)
if all(d > k for k, d in enumerate(days)): # the k-th earliest deadline, from 0, gets day k + 1
top = max(top, sum(profit[i] for i in range(n) if mask >> i & 1))
return top
def greedy(deadline, profit, latest): # the most profitable job first, on its latest (or earliest) free day
used, total = set(), 0
for i in sorted(range(len(profit)), key=lambda i: -profit[i]):
days = range(deadline[i], 0, -1) if latest else range(1, deadline[i] + 1)
day = next((d for d in days if d not in used), 0)
if day:
used.add(day)
total += profit[i]
return total
sets = latest_short = earliest_short = 0
for n in range(1, 5):
for deadline in product(range(1, n + 1), repeat=n): # deadlines 1 to n
for profit in permutations(range(1, n + 1)): # profits 1 to n, each once
top = best(deadline, profit)
sets += 1
latest_short += greedy(deadline, profit, True) < top
earliest_short += greedy(deadline, profit, False) < top
print(f"{sets} job sets of 1 to 4 jobs: the latest free day falls short of the best in {latest_short}, "
f"the earliest free day in {earliest_short}")
deadline7, profit7 = [2, 4, 1, 3, 2, 1, 4], [45, 70, 20, 30, 65, 40, 50]
print(f"seven jobs: the best {best(deadline7, profit7)}, the latest free day {greedy(deadline7, profit7, True)}, "
f"the earliest free day {greedy(deadline7, profit7, False)}")
# 6315 job sets of 1 to 4 jobs: the latest free day falls short of the best in 0, the earliest free day in 4184
# seven jobs: the best 230, the latest free day 230, the earliest free day 185import java.util.*;
public class Main {
static int best(int[] deadline, int[] profit) { // every set of jobs: does it fit, and what does it earn?
int n = deadline.length, top = 0;
for (int mask = 0; mask < 1 << n; mask++) {
List<Integer> days = new ArrayList<>();
int sum = 0;
for (int i = 0; i < n; i++)
if ((mask >> i & 1) == 1) {
days.add(deadline[i]);
sum += profit[i];
}
Collections.sort(days);
boolean fits = true;
for (int k = 0; k < days.size(); k++)
if (days.get(k) <= k) fits = false; // the k-th earliest deadline, from 0, gets day k + 1
if (fits) top = Math.max(top, sum);
}
return top;
}
// the most profitable job first, on its latest (or earliest) free day
static int greedy(int[] deadline, int[] profit, boolean latest) {
int n = deadline.length, total = 0;
Integer[] order = new Integer[n];
for (int i = 0; i < n; i++) order[i] = i;
Arrays.sort(order, (a, b) -> profit[b] - profit[a]);
boolean[] used = new boolean[n + 1];
for (int i : order)
for (int k = 0; k < deadline[i]; k++) {
int d = latest ? deadline[i] - k : k + 1;
if (!used[d]) {
used[d] = true;
total += profit[i];
break;
}
}
return total;
}
static int[] digits(int code, int n) { // code's n digits in base n, each plus 1
int[] t = new int[n];
for (int i = 0; i < n; i++) {
t[i] = code % n + 1;
code /= n;
}
return t;
}
public static void main(String[] args) {
int sets = 0, latestShort = 0, earliestShort = 0;
for (int n = 1; n <= 4; n++) {
int all = (int) Math.pow(n, n);
for (int a = 0; a < all; a++) {
int[] deadline = digits(a, n); // deadlines 1 to n
for (int b = 0; b < all; b++) {
int[] profit = digits(b, n);
if (Arrays.stream(profit).distinct().count() < n) continue; // profits 1 to n, each once
int top = best(deadline, profit);
sets++;
if (greedy(deadline, profit, true) < top) latestShort++;
if (greedy(deadline, profit, false) < top) earliestShort++;
}
}
}
System.out.println(sets + " job sets of 1 to 4 jobs: the latest free day falls short of the best in "
+ latestShort + ", the earliest free day in " + earliestShort);
int[] deadline7 = {2, 4, 1, 3, 2, 1, 4}, profit7 = {45, 70, 20, 30, 65, 40, 50};
System.out.println("seven jobs: the best " + best(deadline7, profit7) + ", the latest free day "
+ greedy(deadline7, profit7, true) + ", the earliest free day " + greedy(deadline7, profit7, false));
}
}
// 6315 job sets of 1 to 4 jobs: the latest free day falls short of the best in 0, the earliest free day in 4184
// seven jobs: the best 230, the latest free day 230, the earliest free day 185#include <bits/stdc++.h>
using namespace std;
int best(const vector<int>& deadline, const vector<int>& profit) { // every set of jobs: does it fit, and what does it earn?
int n = deadline.size(), top = 0;
for (int mask = 0; mask < 1 << n; mask++) {
vector<int> days;
int sum = 0;
for (int i = 0; i < n; i++)
if (mask >> i & 1) {
days.push_back(deadline[i]);
sum += profit[i];
}
sort(days.begin(), days.end());
bool fits = true;
for (int k = 0; k < (int)days.size(); k++)
if (days[k] <= k) fits = false; // the k-th earliest deadline, from 0, gets day k + 1
if (fits) top = max(top, sum);
}
return top;
}
// the most profitable job first, on its latest (or earliest) free day
int greedy(const vector<int>& deadline, const vector<int>& profit, bool latest) {
int n = deadline.size(), total = 0;
vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int a, int b) { return profit[a] > profit[b]; });
vector<bool> used(n + 1);
for (int i : order)
for (int k = 0; k < deadline[i]; k++) {
int d = latest ? deadline[i] - k : k + 1;
if (!used[d]) {
used[d] = true;
total += profit[i];
break;
}
}
return total;
}
vector<int> digits(int code, int n) { // code's n digits in base n, each plus 1
vector<int> t(n);
for (int i = 0; i < n; i++) {
t[i] = code % n + 1;
code /= n;
}
return t;
}
int main() {
int sets = 0, latestShort = 0, earliestShort = 0;
for (int n = 1; n <= 4; n++) {
int all = 1;
for (int i = 0; i < n; i++) all *= n;
for (int a = 0; a < all; a++) {
vector<int> deadline = digits(a, n); // deadlines 1 to n
for (int b = 0; b < all; b++) {
vector<int> profit = digits(b, n);
if ((int)set<int>(profit.begin(), profit.end()).size() < n) continue; // profits 1 to n, each once
int top = best(deadline, profit);
sets++;
if (greedy(deadline, profit, true) < top) latestShort++;
if (greedy(deadline, profit, false) < top) earliestShort++;
}
}
}
cout << sets << " job sets of 1 to 4 jobs: the latest free day falls short of the best in " << latestShort
<< ", the earliest free day in " << earliestShort << "\n";
vector<int> deadline7 = {2, 4, 1, 3, 2, 1, 4}, profit7 = {45, 70, 20, 30, 65, 40, 50};
cout << "seven jobs: the best " << best(deadline7, profit7) << ", the latest free day "
<< greedy(deadline7, profit7, true) << ", the earliest free day " << greedy(deadline7, profit7, false) << "\n";
}
// 6315 job sets of 1 to 4 jobs: the latest free day falls short of the best in 0, the earliest free day in 4184
// seven jobs: the best 230, the latest free day 230, the earliest free day 185function best(deadline, profit) { // every set of jobs: does it fit, and what does it earn?
const n = deadline.length;
let top = 0;
for (let mask = 0; mask < 1 << n; mask++) {
const days = [];
let sum = 0;
for (let i = 0; i < n; i++)
if (mask >> i & 1) {
days.push(deadline[i]);
sum += profit[i];
}
days.sort((a, b) => a - b);
if (days.every((d, k) => d > k)) top = Math.max(top, sum); // the k-th earliest deadline, from 0, gets day k + 1
}
return top;
}
function greedy(deadline, profit, latest) { // the most profitable job first, on its latest (or earliest) free day
const order = [...profit.keys()].sort((a, b) => profit[b] - profit[a]);
const used = new Array(deadline.length + 1).fill(false);
let total = 0;
for (const i of order)
for (let k = 0; k < deadline[i]; k++) {
const d = latest ? deadline[i] - k : k + 1;
if (!used[d]) {
used[d] = true;
total += profit[i];
break;
}
}
return total;
}
const digits = (code, n) => Array.from({ length: n }, (_, i) => Math.floor(code / n ** i) % n + 1);
let sets = 0, latestShort = 0, earliestShort = 0;
for (let n = 1; n <= 4; n++)
for (let a = 0; a < n ** n; a++) {
const deadline = digits(a, n); // deadlines 1 to n
for (let b = 0; b < n ** n; b++) {
const profit = digits(b, n);
if (new Set(profit).size < n) continue; // profits 1 to n, each once
const top = best(deadline, profit);
sets++;
if (greedy(deadline, profit, true) < top) latestShort++;
if (greedy(deadline, profit, false) < top) earliestShort++;
}
}
console.log(`${sets} job sets of 1 to 4 jobs: the latest free day falls short of the best in ${latestShort}, the earliest free day in ${earliestShort}`);
const deadline7 = [2, 4, 1, 3, 2, 1, 4], profit7 = [45, 70, 20, 30, 65, 40, 50];
console.log(`seven jobs: the best ${best(deadline7, profit7)}, the latest free day ${greedy(deadline7, profit7, true)}, the earliest free day ${greedy(deadline7, profit7, false)}`);
// 6315 job sets of 1 to 4 jobs: the latest free day falls short of the best in 0, the earliest free day in 4184
// seven jobs: the best 230, the latest free day 230, the earliest free day 185function best(deadline: number[], profit: number[]): number { // every set of jobs: does it fit, and what does it earn?
const n = deadline.length;
let top = 0;
for (let mask = 0; mask < 1 << n; mask++) {
const days: number[] = [];
let sum = 0;
for (let i = 0; i < n; i++)
if (mask >> i & 1) {
days.push(deadline[i]);
sum += profit[i];
}
days.sort((a, b) => a - b);
if (days.every((d, k) => d > k)) top = Math.max(top, sum); // the k-th earliest deadline, from 0, gets day k + 1
}
return top;
}
// the most profitable job first, on its latest (or earliest) free day
function greedy(deadline: number[], profit: number[], latest: boolean): number {
const order = [...profit.keys()].sort((a, b) => profit[b] - profit[a]);
const used: boolean[] = new Array(deadline.length + 1).fill(false);
let total = 0;
for (const i of order)
for (let k = 0; k < deadline[i]; k++) {
const d = latest ? deadline[i] - k : k + 1;
if (!used[d]) {
used[d] = true;
total += profit[i];
break;
}
}
return total;
}
const digits = (code: number, n: number): number[] =>
Array.from({ length: n }, (_, i) => Math.floor(code / n ** i) % n + 1);
let sets = 0, latestShort = 0, earliestShort = 0;
for (let n = 1; n <= 4; n++)
for (let a = 0; a < n ** n; a++) {
const deadline = digits(a, n); // deadlines 1 to n
for (let b = 0; b < n ** n; b++) {
const profit = digits(b, n);
if (new Set(profit).size < n) continue; // profits 1 to n, each once
const top = best(deadline, profit);
sets++;
if (greedy(deadline, profit, true) < top) latestShort++;
if (greedy(deadline, profit, false) < top) earliestShort++;
}
}
console.log(`${sets} job sets of 1 to 4 jobs: the latest free day falls short of the best in ${latestShort}, the earliest free day in ${earliestShort}`);
const deadline7 = [2, 4, 1, 3, 2, 1, 4], profit7 = [45, 70, 20, 30, 65, 40, 50];
console.log(`seven jobs: the best ${best(deadline7, profit7)}, the latest free day ${greedy(deadline7, profit7, true)}, the earliest free day ${greedy(deadline7, profit7, false)}`);
// 6315 job sets of 1 to 4 jobs: the latest free day falls short of the best in 0, the earliest free day in 4184
// seven jobs: the best 230, the latest free day 230, the earliest free day 185using System;
using System.Collections.Generic;
using System.Linq;
class Program {
static int Best(int[] deadline, int[] profit) { // every set of jobs: does it fit, and what does it earn?
int n = deadline.Length, top = 0;
for (int mask = 0; mask < 1 << n; mask++) {
var days = new List<int>();
int sum = 0;
for (int i = 0; i < n; i++)
if ((mask >> i & 1) == 1) {
days.Add(deadline[i]);
sum += profit[i];
}
days.Sort();
bool fits = true;
for (int k = 0; k < days.Count; k++)
if (days[k] <= k) fits = false; // the k-th earliest deadline, from 0, gets day k + 1
if (fits) top = Math.Max(top, sum);
}
return top;
}
// the most profitable job first, on its latest (or earliest) free day
static int Greedy(int[] deadline, int[] profit, bool latest) {
int n = deadline.Length, total = 0;
var order = Enumerable.Range(0, n).OrderByDescending(i => profit[i]).ToArray();
var used = new bool[n + 1];
foreach (int i in order)
for (int k = 0; k < deadline[i]; k++) {
int d = latest ? deadline[i] - k : k + 1;
if (!used[d]) {
used[d] = true;
total += profit[i];
break;
}
}
return total;
}
static int[] Digits(int code, int n) { // code's n digits in base n, each plus 1
var t = new int[n];
for (int i = 0; i < n; i++) {
t[i] = code % n + 1;
code /= n;
}
return t;
}
static void Main() {
int sets = 0, latestShort = 0, earliestShort = 0;
for (int n = 1; n <= 4; n++) {
int all = (int)Math.Pow(n, n);
for (int a = 0; a < all; a++) {
int[] deadline = Digits(a, n); // deadlines 1 to n
for (int b = 0; b < all; b++) {
int[] profit = Digits(b, n);
if (profit.Distinct().Count() < n) continue; // profits 1 to n, each once
int top = Best(deadline, profit);
sets++;
if (Greedy(deadline, profit, true) < top) latestShort++;
if (Greedy(deadline, profit, false) < top) earliestShort++;
}
}
}
Console.WriteLine($"{sets} job sets of 1 to 4 jobs: the latest free day falls short of the best in {latestShort}, the earliest free day in {earliestShort}");
int[] deadline7 = { 2, 4, 1, 3, 2, 1, 4 }, profit7 = { 45, 70, 20, 30, 65, 40, 50 };
Console.WriteLine($"seven jobs: the best {Best(deadline7, profit7)}, the latest free day {Greedy(deadline7, profit7, true)}, the earliest free day {Greedy(deadline7, profit7, false)}");
}
}
// 6315 job sets of 1 to 4 jobs: the latest free day falls short of the best in 0, the earliest free day in 4184
// seven jobs: the best 230, the latest free day 230, the earliest free day 185package main
import (
"fmt"
"sort"
)
func best(deadline, profit []int) int { // every set of jobs: does it fit, and what does it earn?
n, top := len(deadline), 0
for mask := 0; mask < 1<<n; mask++ {
var days []int
sum := 0
for i := 0; i < n; i++ {
if mask>>i&1 == 1 {
days = append(days, deadline[i])
sum += profit[i]
}
}
sort.Ints(days)
fits := true
for k, d := range days {
if d <= k { // the k-th earliest deadline, from 0, gets day k + 1
fits = false
}
}
if fits && sum > top {
top = sum
}
}
return top
}
// the most profitable job first, on its latest (or earliest) free day
func greedy(deadline, profit []int, latest bool) int {
n, total := len(deadline), 0
order := make([]int, n)
for i := range order {
order[i] = i
}
sort.Slice(order, func(a, b int) bool { return profit[order[a]] > profit[order[b]] })
used := make([]bool, n+1)
for _, i := range order {
for k := 0; k < deadline[i]; k++ {
d := k + 1
if latest {
d = deadline[i] - k
}
if !used[d] {
used[d] = true
total += profit[i]
break
}
}
}
return total
}
func digits(code, n int) []int { // code's n digits in base n, each plus 1
t := make([]int, n)
for i := range t {
t[i] = code%n + 1
code /= n
}
return t
}
func main() {
sets, latestShort, earliestShort := 0, 0, 0
for n := 1; n <= 4; n++ {
all := 1
for i := 0; i < n; i++ {
all *= n
}
for a := 0; a < all; a++ {
deadline := digits(a, n) // deadlines 1 to n
for b := 0; b < all; b++ {
profit := digits(b, n)
seen := map[int]bool{}
for _, p := range profit {
seen[p] = true
}
if len(seen) < n {
continue // profits 1 to n, each once
}
top := best(deadline, profit)
sets++
if greedy(deadline, profit, true) < top {
latestShort++
}
if greedy(deadline, profit, false) < top {
earliestShort++
}
}
}
}
fmt.Printf("%d job sets of 1 to 4 jobs: the latest free day falls short of the best in %d, the earliest free day in %d\n",
sets, latestShort, earliestShort)
deadline7, profit7 := []int{2, 4, 1, 3, 2, 1, 4}, []int{45, 70, 20, 30, 65, 40, 50}
fmt.Printf("seven jobs: the best %d, the latest free day %d, the earliest free day %d\n",
best(deadline7, profit7), greedy(deadline7, profit7, true), greedy(deadline7, profit7, false))
}
// 6315 job sets of 1 to 4 jobs: the latest free day falls short of the best in 0, the earliest free day in 4184
// seven jobs: the best 230, the latest free day 230, the earliest free day 185The latest free day is never short of the best: 0 of the 6,315 sets. The earliest free day falls short in 4,184, about two sets in three. On the seven jobs the latest free day earns 230, the best there is, and the earliest 185. A late day suits few jobs, only those due that late, while day 1 suits every job. Spend the late days first, and the early ones stay free for the jobs that need them.
The latest free day
Job Sequencing Problem asks for that schedule and returns how many jobs it does and what they earn. Sort the jobs by profit, the most first. For each, start at its deadline and step back a day at a time to the first free day; if every day up to the deadline is taken, skip the job. The seven jobs, numbered from 0:
def schedule(deadline, profit): # the most profitable job first, on the latest free day by its deadline
day_of = [None] * (max(deadline) + 1) # day_of[d]: the job done on day d
for i in sorted(range(len(profit)), key=lambda i: -profit[i]):
for d in range(deadline[i], 0, -1): # its deadline, then back a day at a time
if day_of[d] is None:
day_of[d] = i
break
jobs = [i for i in day_of[1:] if i is not None]
return day_of, [len(jobs), sum(profit[i] for i in jobs)]
deadline = [2, 4, 1, 3, 2, 1, 4]
profit = [45, 70, 20, 30, 65, 40, 50]
day_of, answer = schedule(deadline, profit)
print(", ".join(f"day {d}: job {i}" for d, i in enumerate(day_of) if d and i is not None), answer)
# day 1: job 0, day 2: job 4, day 3: job 6, day 4: job 1 [4, 230]import java.util.*;
public class Main {
// the most profitable job first, on the latest free day by its deadline; dayOf[d]: the job done on day d, or -1
static int[] schedule(int[] deadline, int[] profit, int[] dayOf) {
Arrays.fill(dayOf, -1);
Integer[] order = new Integer[profit.length];
for (int i = 0; i < order.length; i++) order[i] = i;
Arrays.sort(order, (a, b) -> profit[b] - profit[a]);
int count = 0, total = 0;
for (int i : order)
for (int d = deadline[i]; d > 0; d--) // its deadline, then back a day at a time
if (dayOf[d] == -1) {
dayOf[d] = i;
count++;
total += profit[i];
break;
}
return new int[] {count, total};
}
public static void main(String[] args) {
int[] deadline = {2, 4, 1, 3, 2, 1, 4};
int[] profit = {45, 70, 20, 30, 65, 40, 50};
int[] dayOf = new int[Arrays.stream(deadline).max().getAsInt() + 1];
int[] answer = schedule(deadline, profit, dayOf);
StringJoiner days = new StringJoiner(", ");
for (int d = 1; d < dayOf.length; d++)
if (dayOf[d] != -1) days.add("day " + d + ": job " + dayOf[d]);
System.out.println(days + " " + Arrays.toString(answer));
}
}
// day 1: job 0, day 2: job 4, day 3: job 6, day 4: job 1 [4, 230]#include <bits/stdc++.h>
using namespace std;
// the most profitable job first, on the latest free day by its deadline; dayOf[d]: the job done on day d, or -1
vector<int> schedule(const vector<int>& deadline, const vector<int>& profit, vector<int>& dayOf) {
dayOf.assign(*max_element(deadline.begin(), deadline.end()) + 1, -1);
vector<int> order(profit.size());
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int a, int b) { return profit[a] > profit[b]; });
int count = 0, total = 0;
for (int i : order)
for (int d = deadline[i]; d > 0; d--) // its deadline, then back a day at a time
if (dayOf[d] == -1) {
dayOf[d] = i;
count++;
total += profit[i];
break;
}
return {count, total};
}
int main() {
vector<int> deadline = {2, 4, 1, 3, 2, 1, 4};
vector<int> profit = {45, 70, 20, 30, 65, 40, 50};
vector<int> dayOf;
vector<int> answer = schedule(deadline, profit, dayOf);
string days;
for (int d = 1; d < (int)dayOf.size(); d++)
if (dayOf[d] != -1) days += (days.empty() ? "" : ", ") + string("day ") + to_string(d) + ": job " + to_string(dayOf[d]);
cout << days << " [" << answer[0] << ", " << answer[1] << "]\n";
}
// day 1: job 0, day 2: job 4, day 3: job 6, day 4: job 1 [4, 230]function schedule(deadline, profit) { // the most profitable job first, on the latest free day by its deadline
const dayOf = new Array(Math.max(...deadline) + 1).fill(-1); // dayOf[d]: the job done on day d, or -1
const order = [...profit.keys()].sort((a, b) => profit[b] - profit[a]);
let count = 0, total = 0;
for (const i of order)
for (let d = deadline[i]; d > 0; d--) // its deadline, then back a day at a time
if (dayOf[d] === -1) {
dayOf[d] = i;
count++;
total += profit[i];
break;
}
return { dayOf, answer: [count, total] };
}
const deadline = [2, 4, 1, 3, 2, 1, 4];
const profit = [45, 70, 20, 30, 65, 40, 50];
const { dayOf, answer } = schedule(deadline, profit);
const days = dayOf.flatMap((i, d) => (d && i !== -1 ? [`day ${d}: job ${i}`] : []));
console.log(`${days.join(", ")} [${answer.join(", ")}]`);
// day 1: job 0, day 2: job 4, day 3: job 6, day 4: job 1 [4, 230]// the most profitable job first, on the latest free day by its deadline
function schedule(deadline: number[], profit: number[]): { dayOf: number[]; answer: number[] } {
const dayOf: number[] = new Array(Math.max(...deadline) + 1).fill(-1); // dayOf[d]: the job done on day d, or -1
const order = [...profit.keys()].sort((a, b) => profit[b] - profit[a]);
let count = 0, total = 0;
for (const i of order)
for (let d = deadline[i]; d > 0; d--) // its deadline, then back a day at a time
if (dayOf[d] === -1) {
dayOf[d] = i;
count++;
total += profit[i];
break;
}
return { dayOf, answer: [count, total] };
}
const deadline = [2, 4, 1, 3, 2, 1, 4];
const profit = [45, 70, 20, 30, 65, 40, 50];
const { dayOf, answer } = schedule(deadline, profit);
const days = dayOf.flatMap((i, d) => (d && i !== -1 ? [`day ${d}: job ${i}`] : []));
console.log(`${days.join(", ")} [${answer.join(", ")}]`);
// day 1: job 0, day 2: job 4, day 3: job 6, day 4: job 1 [4, 230]using System;
using System.Linq;
class Program {
// the most profitable job first, on the latest free day by its deadline; dayOf[d]: the job done on day d, or -1
static int[] Schedule(int[] deadline, int[] profit, int[] dayOf) {
Array.Fill(dayOf, -1);
var order = Enumerable.Range(0, profit.Length).OrderByDescending(i => profit[i]);
int count = 0, total = 0;
foreach (int i in order)
for (int d = deadline[i]; d > 0; d--) // its deadline, then back a day at a time
if (dayOf[d] == -1) {
dayOf[d] = i;
count++;
total += profit[i];
break;
}
return new[] { count, total };
}
static void Main() {
int[] deadline = { 2, 4, 1, 3, 2, 1, 4 };
int[] profit = { 45, 70, 20, 30, 65, 40, 50 };
var dayOf = new int[deadline.Max() + 1];
int[] answer = Schedule(deadline, profit, dayOf);
var days = Enumerable.Range(1, dayOf.Length - 1).Where(d => dayOf[d] != -1).Select(d => $"day {d}: job {dayOf[d]}");
Console.WriteLine($"{string.Join(", ", days)} [{answer[0]}, {answer[1]}]");
}
}
// day 1: job 0, day 2: job 4, day 3: job 6, day 4: job 1 [4, 230]package main
import (
"fmt"
"sort"
"strings"
)
// the most profitable job first, on the latest free day by its deadline; dayOf[d]: the job done on day d, or -1
func schedule(deadline, profit []int) ([]int, [2]int) {
last := 0
for _, d := range deadline {
if d > last {
last = d
}
}
dayOf := make([]int, last+1)
for d := range dayOf {
dayOf[d] = -1
}
order := make([]int, len(profit))
for i := range order {
order[i] = i
}
sort.Slice(order, func(a, b int) bool { return profit[order[a]] > profit[order[b]] })
count, total := 0, 0
for _, i := range order {
for d := deadline[i]; d > 0; d-- { // its deadline, then back a day at a time
if dayOf[d] == -1 {
dayOf[d] = i
count++
total += profit[i]
break
}
}
}
return dayOf, [2]int{count, total}
}
func main() {
deadline := []int{2, 4, 1, 3, 2, 1, 4}
profit := []int{45, 70, 20, 30, 65, 40, 50}
dayOf, answer := schedule(deadline, profit)
var days []string
for d := 1; d < len(dayOf); d++ {
if dayOf[d] != -1 {
days = append(days, fmt.Sprintf("day %d: job %d", d, dayOf[d]))
}
}
fmt.Printf("%s [%d, %d]\n", strings.Join(days, ", "), answer[0], answer[1])
}
// day 1: job 0, day 2: job 4, day 3: job 6, day 4: job 1 [4, 230]Job 1, worth 70 and due by day 4, takes day 4. Job 4, worth 65 and due by day 2, takes day 2. Job 6 is due by day 4, which is taken, so it steps back to day 3. Job 0 is due by day 2, also taken, so it gets day 1. The jobs worth 40, 30 and 20 find every day up to their deadlines taken. 4 jobs for 230, every day used.
Taking the most profitable job first is safe: if a best schedule left job 1 out, putting it on a day by its deadline, in place of whatever is there, can't lose, as nothing earns more. Its day is safe too: the latest free one is the day the fewest of the jobs still to come could use. That's the exchange argument of Introduction to Greedy Algorithms, once for the job and once for the day.
Free days in one jump
Stepping back a day at a time is slow when many jobs share a deadline: each one walks past every day already taken, and Job Sequencing Problem allows 100,000 jobs, due as late as day 100,000. Give each day a pointer instead. A free day points at itself; a used day points at the day before it. From a job's deadline, follow the pointers until a day points at itself: that's the latest free day, or day 0, none left. Then point every day you passed straight at it, so the next search skips them all. On 4,000 jobs, every one due on day 4,000:
def by_scan(deadline, profit): # back a day at a time from the deadline
used, total, steps = [False] * (max(deadline) + 1), 0, 0
for i in sorted(range(len(profit)), key=lambda i: -profit[i]):
d = deadline[i]
while d > 0 and used[d]:
d -= 1
steps += 1
if d:
used[d] = True
total += profit[i]
return total, steps
def by_pointers(deadline, profit): # free[d]: where to look for the latest free day up to d; 0 is none
free = list(range(max(deadline) + 1)) # at first every day is free and points at itself
total = steps = 0
for i in sorted(range(len(profit)), key=lambda i: -profit[i]):
d, path = deadline[i], []
while free[d] != d: # follow the pointers to a day that points at itself
path.append(d)
d = free[d]
steps += 1
for p in path: # every day passed now points straight at it
free[p] = d
if d:
free[d] = d - 1 # used: from now on it points at the day before
total += profit[i]
return total, steps
n = 4000
deadline = [n] * n # every job due on the last day
profit = [i % 100 + 1 for i in range(n)]
scan, pointers = by_scan(deadline, profit), by_pointers(deadline, profit)
print(f"{n} jobs, every deadline {n}: scanning back earns {scan[0]} in {scan[1]} steps; "
f"the pointers earn {pointers[0]} in {pointers[1]} steps")
# 4000 jobs, every deadline 4000: scanning back earns 202000 in 7998000 steps; the pointers earn 202000 in 7997 stepsimport java.util.*;
public class Main {
static Integer[] byProfit(int[] profit) { // the jobs, the most profitable first
Integer[] order = new Integer[profit.length];
for (int i = 0; i < order.length; i++) order[i] = i;
Arrays.sort(order, (a, b) -> profit[b] - profit[a]);
return order;
}
static long[] byScan(int[] deadline, int[] profit) { // back a day at a time from the deadline
boolean[] used = new boolean[Arrays.stream(deadline).max().getAsInt() + 1];
long total = 0, steps = 0;
for (int i : byProfit(profit)) {
int d = deadline[i];
while (d > 0 && used[d]) {
d--;
steps++;
}
if (d > 0) {
used[d] = true;
total += profit[i];
}
}
return new long[] {total, steps};
}
// free[d]: where to look for the latest free day up to d; 0 is none
static long[] byPointers(int[] deadline, int[] profit) {
int[] free = new int[Arrays.stream(deadline).max().getAsInt() + 1];
for (int d = 0; d < free.length; d++) free[d] = d; // at first every day is free and points at itself
long total = 0, steps = 0;
List<Integer> path = new ArrayList<>();
for (int i : byProfit(profit)) {
int d = deadline[i];
path.clear();
while (free[d] != d) { // follow the pointers to a day that points at itself
path.add(d);
d = free[d];
steps++;
}
for (int p : path) free[p] = d; // every day passed now points straight at it
if (d > 0) {
free[d] = d - 1; // used: from now on it points at the day before
total += profit[i];
}
}
return new long[] {total, steps};
}
public static void main(String[] args) {
int n = 4000;
int[] deadline = new int[n], profit = new int[n];
for (int i = 0; i < n; i++) {
deadline[i] = n; // every job due on the last day
profit[i] = i % 100 + 1;
}
long[] scan = byScan(deadline, profit), pointers = byPointers(deadline, profit);
System.out.println(n + " jobs, every deadline " + n + ": scanning back earns " + scan[0] + " in " + scan[1]
+ " steps; the pointers earn " + pointers[0] + " in " + pointers[1] + " steps");
}
}
// 4000 jobs, every deadline 4000: scanning back earns 202000 in 7998000 steps; the pointers earn 202000 in 7997 steps#include <bits/stdc++.h>
using namespace std;
vector<int> byProfit(const vector<int>& profit) { // the jobs, the most profitable first
vector<int> order(profit.size());
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int a, int b) { return profit[a] > profit[b]; });
return order;
}
pair<long long, long long> byScan(const vector<int>& deadline, const vector<int>& profit) { // back a day at a time
vector<bool> used(*max_element(deadline.begin(), deadline.end()) + 1);
long long total = 0, steps = 0;
for (int i : byProfit(profit)) {
int d = deadline[i];
while (d > 0 && used[d]) {
d--;
steps++;
}
if (d > 0) {
used[d] = true;
total += profit[i];
}
}
return {total, steps};
}
// free[d]: where to look for the latest free day up to d; 0 is none
pair<long long, long long> byPointers(const vector<int>& deadline, const vector<int>& profit) {
vector<int> free(*max_element(deadline.begin(), deadline.end()) + 1);
iota(free.begin(), free.end(), 0); // at first every day is free and points at itself
long long total = 0, steps = 0;
vector<int> path;
for (int i : byProfit(profit)) {
int d = deadline[i];
path.clear();
while (free[d] != d) { // follow the pointers to a day that points at itself
path.push_back(d);
d = free[d];
steps++;
}
for (int p : path) free[p] = d; // every day passed now points straight at it
if (d > 0) {
free[d] = d - 1; // used: from now on it points at the day before
total += profit[i];
}
}
return {total, steps};
}
int main() {
int n = 4000;
vector<int> deadline(n, n), profit(n); // every job due on the last day
for (int i = 0; i < n; i++) profit[i] = i % 100 + 1;
auto scan = byScan(deadline, profit);
auto pointers = byPointers(deadline, profit);
cout << n << " jobs, every deadline " << n << ": scanning back earns " << scan.first << " in " << scan.second
<< " steps; the pointers earn " << pointers.first << " in " << pointers.second << " steps\n";
}
// 4000 jobs, every deadline 4000: scanning back earns 202000 in 7998000 steps; the pointers earn 202000 in 7997 stepsconst byProfit = (profit) => [...profit.keys()].sort((a, b) => profit[b] - profit[a]); // the most profitable first
function byScan(deadline, profit) { // back a day at a time from the deadline
const used = new Array(Math.max(...deadline) + 1).fill(false);
let total = 0, steps = 0;
for (const i of byProfit(profit)) {
let d = deadline[i];
while (d > 0 && used[d]) {
d--;
steps++;
}
if (d > 0) {
used[d] = true;
total += profit[i];
}
}
return [total, steps];
}
function byPointers(deadline, profit) { // free[d]: where to look for the latest free day up to d; 0 is none
const free = [...Array(Math.max(...deadline) + 1).keys()]; // at first every day is free and points at itself
let total = 0, steps = 0;
for (const i of byProfit(profit)) {
let d = deadline[i];
const path = [];
while (free[d] !== d) { // follow the pointers to a day that points at itself
path.push(d);
d = free[d];
steps++;
}
for (const p of path) free[p] = d; // every day passed now points straight at it
if (d > 0) {
free[d] = d - 1; // used: from now on it points at the day before
total += profit[i];
}
}
return [total, steps];
}
const n = 4000;
const deadline = new Array(n).fill(n); // every job due on the last day
const profit = Array.from({ length: n }, (_, i) => i % 100 + 1);
const scan = byScan(deadline, profit), pointers = byPointers(deadline, profit);
console.log(`${n} jobs, every deadline ${n}: scanning back earns ${scan[0]} in ${scan[1]} steps; the pointers earn ${pointers[0]} in ${pointers[1]} steps`);
// 4000 jobs, every deadline 4000: scanning back earns 202000 in 7998000 steps; the pointers earn 202000 in 7997 stepsconst byProfit = (profit: number[]): number[] => [...profit.keys()].sort((a, b) => profit[b] - profit[a]);
function byScan(deadline: number[], profit: number[]): [number, number] { // back a day at a time from the deadline
const used: boolean[] = new Array(Math.max(...deadline) + 1).fill(false);
let total = 0, steps = 0;
for (const i of byProfit(profit)) {
let d = deadline[i];
while (d > 0 && used[d]) {
d--;
steps++;
}
if (d > 0) {
used[d] = true;
total += profit[i];
}
}
return [total, steps];
}
// free[d]: where to look for the latest free day up to d; 0 is none
function byPointers(deadline: number[], profit: number[]): [number, number] {
const free = [...Array(Math.max(...deadline) + 1).keys()]; // at first every day is free and points at itself
let total = 0, steps = 0;
for (const i of byProfit(profit)) {
let d = deadline[i];
const path: number[] = [];
while (free[d] !== d) { // follow the pointers to a day that points at itself
path.push(d);
d = free[d];
steps++;
}
for (const p of path) free[p] = d; // every day passed now points straight at it
if (d > 0) {
free[d] = d - 1; // used: from now on it points at the day before
total += profit[i];
}
}
return [total, steps];
}
const n = 4000;
const deadline: number[] = new Array(n).fill(n); // every job due on the last day
const profit = Array.from({ length: n }, (_, i) => i % 100 + 1);
const scan = byScan(deadline, profit), pointers = byPointers(deadline, profit);
console.log(`${n} jobs, every deadline ${n}: scanning back earns ${scan[0]} in ${scan[1]} steps; the pointers earn ${pointers[0]} in ${pointers[1]} steps`);
// 4000 jobs, every deadline 4000: scanning back earns 202000 in 7998000 steps; the pointers earn 202000 in 7997 stepsusing System;
using System.Collections.Generic;
using System.Linq;
class Program {
static int[] ByProfit(int[] profit) => // the jobs, the most profitable first
Enumerable.Range(0, profit.Length).OrderByDescending(i => profit[i]).ToArray();
static (long, long) ByScan(int[] deadline, int[] profit) { // back a day at a time from the deadline
var used = new bool[deadline.Max() + 1];
long total = 0, steps = 0;
foreach (int i in ByProfit(profit)) {
int d = deadline[i];
while (d > 0 && used[d]) {
d--;
steps++;
}
if (d > 0) {
used[d] = true;
total += profit[i];
}
}
return (total, steps);
}
// free[d]: where to look for the latest free day up to d; 0 is none
static (long, long) ByPointers(int[] deadline, int[] profit) {
var free = Enumerable.Range(0, deadline.Max() + 1).ToArray(); // at first every day is free and points at itself
long total = 0, steps = 0;
var path = new List<int>();
foreach (int i in ByProfit(profit)) {
int d = deadline[i];
path.Clear();
while (free[d] != d) { // follow the pointers to a day that points at itself
path.Add(d);
d = free[d];
steps++;
}
foreach (int p in path) free[p] = d; // every day passed now points straight at it
if (d > 0) {
free[d] = d - 1; // used: from now on it points at the day before
total += profit[i];
}
}
return (total, steps);
}
static void Main() {
int n = 4000;
var deadline = Enumerable.Repeat(n, n).ToArray(); // every job due on the last day
var profit = Enumerable.Range(0, n).Select(i => i % 100 + 1).ToArray();
var (scanTotal, scanSteps) = ByScan(deadline, profit);
var (pointerTotal, pointerSteps) = ByPointers(deadline, profit);
Console.WriteLine($"{n} jobs, every deadline {n}: scanning back earns {scanTotal} in {scanSteps} steps; the pointers earn {pointerTotal} in {pointerSteps} steps");
}
}
// 4000 jobs, every deadline 4000: scanning back earns 202000 in 7998000 steps; the pointers earn 202000 in 7997 stepspackage main
import (
"fmt"
"sort"
)
func byProfit(profit []int) []int { // the jobs, the most profitable first
order := make([]int, len(profit))
for i := range order {
order[i] = i
}
sort.Slice(order, func(a, b int) bool { return profit[order[a]] > profit[order[b]] })
return order
}
func lastDay(deadline []int) int {
last := 0
for _, d := range deadline {
if d > last {
last = d
}
}
return last
}
func byScan(deadline, profit []int) (int, int) { // back a day at a time from the deadline
used := make([]bool, lastDay(deadline)+1)
total, steps := 0, 0
for _, i := range byProfit(profit) {
d := deadline[i]
for d > 0 && used[d] {
d--
steps++
}
if d > 0 {
used[d] = true
total += profit[i]
}
}
return total, steps
}
// free[d]: where to look for the latest free day up to d; 0 is none
func byPointers(deadline, profit []int) (int, int) {
free := make([]int, lastDay(deadline)+1)
for d := range free {
free[d] = d // at first every day is free and points at itself
}
total, steps := 0, 0
var path []int
for _, i := range byProfit(profit) {
d := deadline[i]
path = path[:0]
for free[d] != d { // follow the pointers to a day that points at itself
path = append(path, d)
d = free[d]
steps++
}
for _, p := range path {
free[p] = d // every day passed now points straight at it
}
if d > 0 {
free[d] = d - 1 // used: from now on it points at the day before
total += profit[i]
}
}
return total, steps
}
func main() {
n := 4000
deadline, profit := make([]int, n), make([]int, n)
for i := range deadline {
deadline[i] = n // every job due on the last day
profit[i] = i%100 + 1
}
scanTotal, scanSteps := byScan(deadline, profit)
pointerTotal, pointerSteps := byPointers(deadline, profit)
fmt.Printf("%d jobs, every deadline %d: scanning back earns %d in %d steps; the pointers earn %d in %d steps\n",
n, n, scanTotal, scanSteps, pointerTotal, pointerSteps)
}
// 4000 jobs, every deadline 4000: scanning back earns 202000 in 7998000 steps; the pointers earn 202000 in 7997 stepsBoth earn 202,000. Scanning back took 7,998,000 steps, one for every taken day passed, which grows with the square of the jobs; the pointers took 7,997, about two a job. It's union-find on a line of days: each used day is joined to the free day before it, and every search shortens the path it walked. With it, the sort is the slow part: O(n log n).
The shortest job first
Shortest Job First Scheduling drops the deadlines. The jobs all arrive at once and run one at a time, and each waits for every job run before it. Which order makes the total wait smallest? Three orders of jobs taking 6, 2, 8 and 3 minutes:
def waits(order): # each job waits for every job run before it
out, clock = [], 0
for b in order:
out.append(clock)
clock += b
return out
bursts = [6, 2, 8, 3]
for name, order in (("as given", bursts), ("shortest first", sorted(bursts)),
("longest first", sorted(bursts, reverse=True))):
w = waits(order)
print(f"{name}: {' '.join(map(str, order))}, waits {' '.join(map(str, w))}, total {sum(w)}, "
f"average {sum(w) // len(w)}")
# as given: 6 2 8 3, waits 0 6 8 16, total 30, average 7
# shortest first: 2 3 6 8, waits 0 2 5 11, total 18, average 4
# longest first: 8 6 3 2, waits 0 8 14 17, total 39, average 9import java.util.*;
import java.util.stream.*;
public class Main {
static int[] waits(int[] order) { // each job waits for every job run before it
int[] out = new int[order.length];
int clock = 0;
for (int i = 0; i < order.length; i++) {
out[i] = clock;
clock += order[i];
}
return out;
}
static String spaced(int[] xs) {
return Arrays.stream(xs).mapToObj(String::valueOf).collect(Collectors.joining(" "));
}
public static void main(String[] args) {
int[] bursts = {6, 2, 8, 3};
int[] shortest = bursts.clone();
Arrays.sort(shortest);
int[] longest = IntStream.range(0, shortest.length).map(i -> shortest[shortest.length - 1 - i]).toArray();
String[] names = {"as given", "shortest first", "longest first"};
int[][] orders = {bursts, shortest, longest};
for (int k = 0; k < 3; k++) {
int[] w = waits(orders[k]);
int total = Arrays.stream(w).sum();
System.out.println(names[k] + ": " + spaced(orders[k]) + ", waits " + spaced(w) + ", total " + total
+ ", average " + total / w.length);
}
}
}
// as given: 6 2 8 3, waits 0 6 8 16, total 30, average 7
// shortest first: 2 3 6 8, waits 0 2 5 11, total 18, average 4
// longest first: 8 6 3 2, waits 0 8 14 17, total 39, average 9#include <bits/stdc++.h>
using namespace std;
vector<int> waits(const vector<int>& order) { // each job waits for every job run before it
vector<int> out;
int clock = 0;
for (int b : order) {
out.push_back(clock);
clock += b;
}
return out;
}
string spaced(const vector<int>& xs) {
string s;
for (int x : xs) s += (s.empty() ? "" : " ") + to_string(x);
return s;
}
int main() {
vector<int> bursts = {6, 2, 8, 3};
vector<int> shortest = bursts, longest = bursts;
sort(shortest.begin(), shortest.end());
sort(longest.rbegin(), longest.rend());
vector<pair<string, vector<int>>> orders = {{"as given", bursts}, {"shortest first", shortest}, {"longest first", longest}};
for (auto& [name, order] : orders) {
vector<int> w = waits(order);
int total = accumulate(w.begin(), w.end(), 0);
cout << name << ": " << spaced(order) << ", waits " << spaced(w) << ", total " << total << ", average "
<< total / (int)w.size() << "\n";
}
}
// as given: 6 2 8 3, waits 0 6 8 16, total 30, average 7
// shortest first: 2 3 6 8, waits 0 2 5 11, total 18, average 4
// longest first: 8 6 3 2, waits 0 8 14 17, total 39, average 9function waits(order) { // each job waits for every job run before it
const out = [];
let clock = 0;
for (const b of order) {
out.push(clock);
clock += b;
}
return out;
}
const bursts = [6, 2, 8, 3];
const orders = [["as given", bursts], ["shortest first", [...bursts].sort((a, b) => a - b)],
["longest first", [...bursts].sort((a, b) => b - a)]];
for (const [name, order] of orders) {
const w = waits(order);
const total = w.reduce((s, x) => s + x, 0);
console.log(`${name}: ${order.join(" ")}, waits ${w.join(" ")}, total ${total}, average ${Math.floor(total / w.length)}`);
}
// as given: 6 2 8 3, waits 0 6 8 16, total 30, average 7
// shortest first: 2 3 6 8, waits 0 2 5 11, total 18, average 4
// longest first: 8 6 3 2, waits 0 8 14 17, total 39, average 9function waits(order: number[]): number[] { // each job waits for every job run before it
const out: number[] = [];
let clock = 0;
for (const b of order) {
out.push(clock);
clock += b;
}
return out;
}
const bursts = [6, 2, 8, 3];
const orders: [string, number[]][] = [["as given", bursts], ["shortest first", [...bursts].sort((a, b) => a - b)],
["longest first", [...bursts].sort((a, b) => b - a)]];
for (const [name, order] of orders) {
const w = waits(order);
const total = w.reduce((s, x) => s + x, 0);
console.log(`${name}: ${order.join(" ")}, waits ${w.join(" ")}, total ${total}, average ${Math.floor(total / w.length)}`);
}
// as given: 6 2 8 3, waits 0 6 8 16, total 30, average 7
// shortest first: 2 3 6 8, waits 0 2 5 11, total 18, average 4
// longest first: 8 6 3 2, waits 0 8 14 17, total 39, average 9using System;
using System.Linq;
class Program {
static int[] Waits(int[] order) { // each job waits for every job run before it
var output = new int[order.Length];
int clock = 0;
for (int i = 0; i < order.Length; i++) {
output[i] = clock;
clock += order[i];
}
return output;
}
static void Main() {
int[] bursts = { 6, 2, 8, 3 };
var orders = new (string, int[])[] {
("as given", bursts), ("shortest first", bursts.OrderBy(b => b).ToArray()),
("longest first", bursts.OrderByDescending(b => b).ToArray()) };
foreach (var (name, order) in orders) {
int[] w = Waits(order);
int total = w.Sum();
Console.WriteLine($"{name}: {string.Join(" ", order)}, waits {string.Join(" ", w)}, total {total}, average {total / w.Length}");
}
}
}
// as given: 6 2 8 3, waits 0 6 8 16, total 30, average 7
// shortest first: 2 3 6 8, waits 0 2 5 11, total 18, average 4
// longest first: 8 6 3 2, waits 0 8 14 17, total 39, average 9package main
import (
"fmt"
"sort"
"strings"
)
func waits(order []int) []int { // each job waits for every job run before it
out, clock := make([]int, len(order)), 0
for i, b := range order {
out[i] = clock
clock += b
}
return out
}
func spaced(xs []int) string {
parts := make([]string, len(xs))
for i, x := range xs {
parts[i] = fmt.Sprint(x)
}
return strings.Join(parts, " ")
}
func main() {
bursts := []int{6, 2, 8, 3}
shortest := append([]int(nil), bursts...)
sort.Ints(shortest)
longest := append([]int(nil), bursts...)
sort.Sort(sort.Reverse(sort.IntSlice(longest)))
names := []string{"as given", "shortest first", "longest first"}
for k, order := range [][]int{bursts, shortest, longest} {
w := waits(order)
total := 0
for _, x := range w {
total += x
}
fmt.Printf("%s: %s, waits %s, total %d, average %d\n", names[k], spaced(order), spaced(w), total, total/len(w))
}
}
// as given: 6 2 8 3, waits 0 6 8 16, total 30, average 7
// shortest first: 2 3 6 8, waits 0 2 5 11, total 18, average 4
// longest first: 8 6 3 2, waits 0 8 14 17, total 39, average 9Shortest first waits 18 in all, 4 on average once rounded down, as the problem asks; the order given waits 30, and longest first 39. The proof is a swap of neighbours. If a longer job a runs just before a shorter job b, swap them: b now waits a less, a waits b more, and every other job waits as before, so the total drops by a − b. Any order with a longer job just before a shorter one can be beaten, so the best order has none: shortest first. Jobs that arrive at different times need a heap of the ones that have arrived: Merging and Scheduling with a Heap.
Schedule the Jobs Book the seven jobs yourself, the most profitable first, each on its latest free day, and see a day taken too early caught; then book them your own way and set the total against 230. Then swap neighbours in a queue of the four jobs and watch the total wait change by the difference of the two.
Spotting it
| The problem | Sort by | Then | Why it's safe |
|---|---|---|---|
| Job Sequencing | Profit, most first | The latest free day | A late day suits fewest jobs |
| Job Sequencing, fast | Profit, most first | Pointers to it | A used day points back |
| Shortest Job First | Time, shortest first | Run in that order | A swap of neighbours |
Near misses: jobs with a fixed start, end and profit leave no day to choose, so Maximum Profit in Job Scheduling is Dynamic Programming over the jobs sorted by end; the most jobs with fixed times is Interval Scheduling: Sort by End Time; jobs arriving over time need a heap.
Mistakes that look right
Two of these run below in every language. The others are just as common:
- The earliest deadline first: it does the most jobs, not the most profit.
- A job's own time in its wait: that's when it finishes; it waits only for the jobs before it.
- The earliest free day: it can take the only day a tighter job had.
- Only the deadline day: if it's taken, step back; an earlier day may be free.
- Days from 0: a job due by day 1 has one day, not two.
def by_profit(deadline, profit): # right: the most profitable job first, on its latest free day
used, count, total = [False] * (max(deadline) + 1), 0, 0
for i in sorted(range(len(profit)), key=lambda i: -profit[i]):
for d in range(deadline[i], 0, -1):
if not used[d]:
used[d], count, total = True, count + 1, total + profit[i]
break
return [count, total]
def by_deadline(deadline, profit): # the mistake: the earliest deadline first, every job that still fits
day, total = 0, 0
for i in sorted(range(len(deadline)), key=lambda i: deadline[i]):
if deadline[i] > day: # it fits: do it the next day
day += 1
total += profit[i]
return [day, total]
def waits(order): # right: each job waits for every job run before it
out, clock = [], 0
for b in order:
out.append(clock)
clock += b
return out
def finishes(order): # the mistake: each job's own time counted too
out, clock = [], 0
for b in order:
clock += b
out.append(clock)
return out
deadline, profit = [2, 4, 1, 3, 2, 1, 4], [45, 70, 20, 30, 65, 40, 50]
print(f"the earliest deadline first: {by_deadline(deadline, profit)}, where the most profitable first gets "
f"{by_profit(deadline, profit)}")
bursts = sorted([6, 2, 8, 3])
print(f"each job's own time counted: average {sum(finishes(bursts)) // len(bursts)}, where the average wait is "
f"{sum(waits(bursts)) // len(bursts)}")
# the earliest deadline first: [4, 165], where the most profitable first gets [4, 230]
# each job's own time counted: average 9, where the average wait is 4import java.util.*;
public class Main {
static Integer[] sortedBy(int n, Comparator<Integer> key) {
Integer[] order = new Integer[n];
for (int i = 0; i < n; i++) order[i] = i;
Arrays.sort(order, key);
return order;
}
static int[] byProfit(int[] deadline, int[] profit) { // right: the most profitable job first, on its latest free day
boolean[] used = new boolean[Arrays.stream(deadline).max().getAsInt() + 1];
int count = 0, total = 0;
for (int i : sortedBy(profit.length, (a, b) -> profit[b] - profit[a]))
for (int d = deadline[i]; d > 0; d--)
if (!used[d]) {
used[d] = true;
count++;
total += profit[i];
break;
}
return new int[] {count, total};
}
// the mistake: the earliest deadline first, every job that still fits
static int[] byDeadline(int[] deadline, int[] profit) {
int day = 0, total = 0;
for (int i : sortedBy(deadline.length, (a, b) -> deadline[a] - deadline[b]))
if (deadline[i] > day) { // it fits: do it the next day
day++;
total += profit[i];
}
return new int[] {day, total};
}
static int totalWait(int[] order, boolean ownTime) { // the mistake counts each job's own time too
int clock = 0, total = 0;
for (int b : order) {
if (ownTime) clock += b;
total += clock;
if (!ownTime) clock += b;
}
return total;
}
public static void main(String[] args) {
int[] deadline = {2, 4, 1, 3, 2, 1, 4}, profit = {45, 70, 20, 30, 65, 40, 50};
System.out.println("the earliest deadline first: " + Arrays.toString(byDeadline(deadline, profit))
+ ", where the most profitable first gets " + Arrays.toString(byProfit(deadline, profit)));
int[] bursts = {6, 2, 8, 3};
Arrays.sort(bursts);
System.out.println("each job's own time counted: average " + totalWait(bursts, true) / bursts.length
+ ", where the average wait is " + totalWait(bursts, false) / bursts.length);
}
}
// the earliest deadline first: [4, 165], where the most profitable first gets [4, 230]
// each job's own time counted: average 9, where the average wait is 4#include <bits/stdc++.h>
using namespace std;
vector<int> byProfit(const vector<int>& deadline, const vector<int>& profit) { // right: the most profitable first
vector<bool> used(*max_element(deadline.begin(), deadline.end()) + 1);
vector<int> order(profit.size());
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int a, int b) { return profit[a] > profit[b]; });
int count = 0, total = 0;
for (int i : order)
for (int d = deadline[i]; d > 0; d--) // on its latest free day
if (!used[d]) {
used[d] = true;
count++;
total += profit[i];
break;
}
return {count, total};
}
// the mistake: the earliest deadline first, every job that still fits
vector<int> byDeadline(const vector<int>& deadline, const vector<int>& profit) {
vector<int> order(deadline.size());
iota(order.begin(), order.end(), 0);
stable_sort(order.begin(), order.end(), [&](int a, int b) { return deadline[a] < deadline[b]; });
int day = 0, total = 0;
for (int i : order)
if (deadline[i] > day) { // it fits: do it the next day
day++;
total += profit[i];
}
return {day, total};
}
int totalWait(const vector<int>& order, bool ownTime) { // the mistake counts each job's own time too
int clock = 0, total = 0;
for (int b : order) {
if (ownTime) clock += b;
total += clock;
if (!ownTime) clock += b;
}
return total;
}
string show(const vector<int>& v) { return "[" + to_string(v[0]) + ", " + to_string(v[1]) + "]"; }
int main() {
vector<int> deadline = {2, 4, 1, 3, 2, 1, 4}, profit = {45, 70, 20, 30, 65, 40, 50};
cout << "the earliest deadline first: " << show(byDeadline(deadline, profit))
<< ", where the most profitable first gets " << show(byProfit(deadline, profit)) << "\n";
vector<int> bursts = {6, 2, 8, 3};
sort(bursts.begin(), bursts.end());
int n = bursts.size();
cout << "each job's own time counted: average " << totalWait(bursts, true) / n << ", where the average wait is "
<< totalWait(bursts, false) / n << "\n";
}
// the earliest deadline first: [4, 165], where the most profitable first gets [4, 230]
// each job's own time counted: average 9, where the average wait is 4function byProfit(deadline, profit) { // right: the most profitable job first, on its latest free day
const used = new Array(Math.max(...deadline) + 1).fill(false);
let count = 0, total = 0;
for (const i of [...profit.keys()].sort((a, b) => profit[b] - profit[a]))
for (let d = deadline[i]; d > 0; d--)
if (!used[d]) {
used[d] = true;
count++;
total += profit[i];
break;
}
return [count, total];
}
function byDeadline(deadline, profit) { // the mistake: the earliest deadline first, every job that still fits
let day = 0, total = 0;
for (const i of [...deadline.keys()].sort((a, b) => deadline[a] - deadline[b]))
if (deadline[i] > day) { // it fits: do it the next day
day++;
total += profit[i];
}
return [day, total];
}
function totalWait(order, ownTime) { // the mistake counts each job's own time too
let clock = 0, total = 0;
for (const b of order) {
if (ownTime) clock += b;
total += clock;
if (!ownTime) clock += b;
}
return total;
}
const deadline = [2, 4, 1, 3, 2, 1, 4], profit = [45, 70, 20, 30, 65, 40, 50];
const show = (v) => `[${v.join(", ")}]`;
console.log(`the earliest deadline first: ${show(byDeadline(deadline, profit))}, where the most profitable first gets ${show(byProfit(deadline, profit))}`);
const bursts = [6, 2, 8, 3].sort((a, b) => a - b);
console.log(`each job's own time counted: average ${Math.floor(totalWait(bursts, true) / bursts.length)}, where the average wait is ${Math.floor(totalWait(bursts, false) / bursts.length)}`);
// the earliest deadline first: [4, 165], where the most profitable first gets [4, 230]
// each job's own time counted: average 9, where the average wait is 4// right: the most profitable job first, on its latest free day
function byProfit(deadline: number[], profit: number[]): number[] {
const used: boolean[] = new Array(Math.max(...deadline) + 1).fill(false);
let count = 0, total = 0;
for (const i of [...profit.keys()].sort((a, b) => profit[b] - profit[a]))
for (let d = deadline[i]; d > 0; d--)
if (!used[d]) {
used[d] = true;
count++;
total += profit[i];
break;
}
return [count, total];
}
// the mistake: the earliest deadline first, every job that still fits
function byDeadline(deadline: number[], profit: number[]): number[] {
let day = 0, total = 0;
for (const i of [...deadline.keys()].sort((a, b) => deadline[a] - deadline[b]))
if (deadline[i] > day) { // it fits: do it the next day
day++;
total += profit[i];
}
return [day, total];
}
function totalWait(order: number[], ownTime: boolean): number { // the mistake counts each job's own time too
let clock = 0, total = 0;
for (const b of order) {
if (ownTime) clock += b;
total += clock;
if (!ownTime) clock += b;
}
return total;
}
const deadline = [2, 4, 1, 3, 2, 1, 4], profit = [45, 70, 20, 30, 65, 40, 50];
const show = (v: number[]): string => `[${v.join(", ")}]`;
console.log(`the earliest deadline first: ${show(byDeadline(deadline, profit))}, where the most profitable first gets ${show(byProfit(deadline, profit))}`);
const bursts = [6, 2, 8, 3].sort((a, b) => a - b);
console.log(`each job's own time counted: average ${Math.floor(totalWait(bursts, true) / bursts.length)}, where the average wait is ${Math.floor(totalWait(bursts, false) / bursts.length)}`);
// the earliest deadline first: [4, 165], where the most profitable first gets [4, 230]
// each job's own time counted: average 9, where the average wait is 4using System;
using System.Linq;
class Program {
static int[] ByProfit(int[] deadline, int[] profit) { // right: the most profitable job first, on its latest free day
var used = new bool[deadline.Max() + 1];
int count = 0, total = 0;
foreach (int i in Enumerable.Range(0, profit.Length).OrderByDescending(i => profit[i]))
for (int d = deadline[i]; d > 0; d--)
if (!used[d]) {
used[d] = true;
count++;
total += profit[i];
break;
}
return new[] { count, total };
}
// the mistake: the earliest deadline first, every job that still fits
static int[] ByDeadline(int[] deadline, int[] profit) {
int day = 0, total = 0;
foreach (int i in Enumerable.Range(0, deadline.Length).OrderBy(i => deadline[i]))
if (deadline[i] > day) { // it fits: do it the next day
day++;
total += profit[i];
}
return new[] { day, total };
}
static int TotalWait(int[] order, bool ownTime) { // the mistake counts each job's own time too
int clock = 0, total = 0;
foreach (int b in order) {
if (ownTime) clock += b;
total += clock;
if (!ownTime) clock += b;
}
return total;
}
static string Show(int[] v) => $"[{string.Join(", ", v)}]";
static void Main() {
int[] deadline = { 2, 4, 1, 3, 2, 1, 4 }, profit = { 45, 70, 20, 30, 65, 40, 50 };
Console.WriteLine($"the earliest deadline first: {Show(ByDeadline(deadline, profit))}, where the most profitable first gets {Show(ByProfit(deadline, profit))}");
int[] bursts = new[] { 6, 2, 8, 3 }.OrderBy(b => b).ToArray();
Console.WriteLine($"each job's own time counted: average {TotalWait(bursts, true) / bursts.Length}, where the average wait is {TotalWait(bursts, false) / bursts.Length}");
}
}
// the earliest deadline first: [4, 165], where the most profitable first gets [4, 230]
// each job's own time counted: average 9, where the average wait is 4package main
import (
"fmt"
"sort"
)
// right: the most profitable job first, on its latest free day
func byProfit(deadline, profit []int) [2]int {
last := 0
for _, d := range deadline {
if d > last {
last = d
}
}
used := make([]bool, last+1)
order := make([]int, len(profit))
for i := range order {
order[i] = i
}
sort.Slice(order, func(a, b int) bool { return profit[order[a]] > profit[order[b]] })
count, total := 0, 0
for _, i := range order {
for d := deadline[i]; d > 0; d-- {
if !used[d] {
used[d] = true
count++
total += profit[i]
break
}
}
}
return [2]int{count, total}
}
// the mistake: the earliest deadline first, every job that still fits
func byDeadline(deadline, profit []int) [2]int {
order := make([]int, len(deadline))
for i := range order {
order[i] = i
}
sort.SliceStable(order, func(a, b int) bool { return deadline[order[a]] < deadline[order[b]] })
day, total := 0, 0
for _, i := range order {
if deadline[i] > day { // it fits: do it the next day
day++
total += profit[i]
}
}
return [2]int{day, total}
}
func totalWait(order []int, ownTime bool) int { // the mistake counts each job's own time too
clock, total := 0, 0
for _, b := range order {
if ownTime {
clock += b
}
total += clock
if !ownTime {
clock += b
}
}
return total
}
func main() {
deadline, profit := []int{2, 4, 1, 3, 2, 1, 4}, []int{45, 70, 20, 30, 65, 40, 50}
d, p := byDeadline(deadline, profit), byProfit(deadline, profit)
fmt.Printf("the earliest deadline first: [%d, %d], where the most profitable first gets [%d, %d]\n", d[0], d[1], p[0], p[1])
bursts := []int{6, 2, 8, 3}
sort.Ints(bursts)
n := len(bursts)
fmt.Printf("each job's own time counted: average %d, where the average wait is %d\n",
totalWait(bursts, true)/n, totalWait(bursts, false)/n)
}
// the earliest deadline first: [4, 165], where the most profitable first gets [4, 230]
// each job's own time counted: average 9, where the average wait is 4The earliest deadline first does as many jobs, 4, but earns 165 where 230 is possible: it spends day 1 on the job worth 20. Counting each job's own time gives an average of 9, when the jobs wait 4 on average: 9 is when they finish, not how long they wait.
Check yourself
Quiz
1 / 6Multiple choice
The most profitable job is due by day 3, and days 1, 2 and 3 are all free. Which day does it get?
Multiple choice
Jobs (deadline, profit): (3, 25), (1, 60), (3, 45), (2, 35), (1, 15), one a day. What's the most they can earn?
Multiple choice
Jobs taking 5, 1, 4 and 2 minutes all arrive at once. Run shortest first: what's the total wait?
Multiple choice
In a queue, a job of 7 minutes runs just before a job of 3. Swap the two: what happens to the total wait?
Multiple choice
With the free-day pointers, what happens when a job takes day 5?
Multiple choice
Jobs have fixed start and end times and a profit, and two can't overlap. Does the most profitable first, on the latest free day, work?
Practice
The problems in this group, each mapped to the idea it trains:
- Job Sequencing Problem: the most profitable first, on the latest free day; pointers to go fast.
- Shortest Job First Scheduling: shortest first, each job waiting for the ones before it.