Greedy Algorithms Scheduling

Job Sequencing with Deadlines

Maximize profit by scheduling jobs with deadlines greedily. Sort jobs by profit descending, then assign each job to the latest available slot before its deadline.

Theory

Job sequencing with deadlines is a greedy algorithm that maximizes profit by scheduling jobs optimally. Each job has a deadline and profit; a job cannot be started after its deadline. The key insight is to process jobs in decreasing order of profit and place each job in the latest available time slot before its deadline.

Greedy Choice: Sort jobs by profit descending. For each job, try to schedule it as late as possible (before deadline) to leave room for other jobs.
Why It Works: By scheduling profitable jobs first, and placing them late, we maximize flexibility for remaining jobs while ensuring maximum total profit.
Time Complexity: O(n² + n log n) — O(n log n) for sorting + O(n × maxDeadline) for scheduling. Can be optimized with Union-Find to O(n log n).
Common Applications:
- Project scheduling with deadlines
- Resource allocation in manufacturing
- Task prioritization in systems
- Maximizing revenue with time constraints

Problem Statement

Given n jobs with profit[i] and deadline[i], compute the maximum profit by scheduling jobs optimally. Each job takes 1 unit of time. Only one job can be done at a time. Use the visualizer to step through the job sequencing algorithm, observing how jobs are scheduled in time slots to maximize total profit.

Greedy Strategy

1. Sort by Profit: Arrange jobs in decreasing order of profit. Ensures highest-value jobs are considered first.

2. Backward Scheduling: For each job, search backward from (deadline - 1) to 0 to find the latest available slot.

3. Slot Assignment: If a free slot exists before the deadline, assign the job there. Otherwise, skip the job (no capacity).

4. Feasibility: This order ensures maximum flexibility — by placing jobs late, we leave early slots for lower-profit jobs.

5. Optimality: Greedy choice of maximum profit first guarantees globally optimal solution for this problem.

schedule_anatomy.svg

schedule.svg — Job Scheduling Timeline

Ready to start

Job Schedule State

jobs_sorted.log

Sorted by Profit (Descending)

Press 'Solve Greedy'

schedule_result.log

Maximum Profit Schedule

Total Profit: 0
—

Jobs Input

jobs.csv

Job	Profit	Deadline	Status
J1	60	2	—
J2	100	3	—
J3	80	2	—
J4	70	3	—
J5	50	1	—

Pseudocode

job_sequencing.pseudo

1FUNCTION JobSequencing(jobs[1..n], maxDeadline):
2
3// Step 1 — Sort jobs by profit in descending order
4SORT jobs BY jobs[i].profit DESCENDING
5
6// Step 2 — Initialize time slot array (all slots free)
7CREATE slot[0..maxDeadline-1] = EMPTY
8totalProfit ← 0
9
10// Step 3 — Greedily assign each job to latest available slot
11FOR i ← 1 TO n DO
12
13// Search backward from (deadline - 1) to find latest free slot
14FOR j ← (jobs[i].deadline - 1) DOWNTO 0 DO
15
16IF slot[j] == EMPTY THEN
17slot[j] ← jobs[i].id          // assign job to this slot
18totalProfit ← totalProfit + jobs[i].profit
19BREAK                          // move to next job
20END IF
21
22END FOR                            // if no slot found, job is skipped
23
24END FOR
25
26// Step 4 — Return result
27RETURN slot, totalProfit
28
29END FUNCTION

Input Array of n jobs, each with id, profit, deadline — plus maxDeadline

Key Invariant Each job is placed in the latest possible free slot before its deadline to preserve early slots for others

Output Filled slot[ ] array with scheduled job IDs and maximum total profit

Algorithm & Implementation

Language:

job_sequencing.c

1#include <stdio.h>
2#include <stdlib.h>
3typedef struct {
4int id, profit, deadline;
5} Job;
6
7int compare(const void *a, const void *b) {
8return ((Job*)b)->profit - ((Job*)a)->profit;
9}
10
11int jobSequencing(Job *jobs, int n, int maxD) {
12qsort(jobs, n, sizeof(Job), compare);
13int *slot = (int *)malloc(maxD * sizeof(int));
14for (int i = 0; i < maxD; i++) slot[i] = -1;
15int profit = 0;
16
17for (int i = 0; i < n; i++) {
18for (int j = jobs[i].deadline - 1; j >= 0; j--) {
19if (slot[j] == -1) {
20slot[j] = jobs[i].id;
21profit += jobs[i].profit;
22break;
23}
24}
25}
26free(slot);
27return profit;
28}

Explanation

1. Job Structure (lines 3-5): typedef struct with id, profit (gain), and deadline (latest time). Encapsulates all job data for sorting and scheduling.

2. Compare Function (lines 7-9): Comparator for qsort() sorting jobs in descending profit order: ((Job*)b)->profit - ((Job*)a)->profit. Ensures highest-profit jobs processed first, greedy choice.

3. Slot Array (lines 13-14): Represents time slots 0 to maxDeadline-1. slot[j] stores job ID scheduled at slot j, initialized to -1 (empty). Each index = one unit of time.

4. Backward Scheduling (lines 17-24): For each sorted job: iterate backward from (deadline-1) to 0. If slot[j] == -1 (empty), place job and break. Backward search ensures latest available slot used, maximizing flexibility for remaining jobs. If no slot available, skip job.

5. Time Complexity O(n² + n log n): qsort() is O(n log n). For each of n jobs, search backward through up to maxDeadline slots: O(n × maxDeadline) = O(n²) worst case. Total: O(n log n + n²) ≈ O(n²). Space O(maxDeadline) for slot array.

job_sequencing.py

1def job_sequencing(jobs, max_deadline):
2"""Maximize profit via greedy scheduling"""
3jobs = sorted(jobs, key=lambda x: x['profit'], reverse=True)
4slot = [None] * max_deadline
5profit = 0
6
7for job in jobs:
8for j in range(job['deadline'] - 1, -1, -1):
9if slot[j] is None:
10slot[j] = job['id']
11profit += job['profit']
12break
13}
14return {'profit': profit, 'schedule': slot}
15
16jobs = [
17{'id': 1, 'profit': 60, 'deadline': 2},
18{'id': 2, 'profit': 100, 'deadline': 3}
19]
20result = job_sequencing(jobs, 4)
21print('Profit:', result['profit'])

Explanation

1. Function Signature (lines 1-2): job_sequencing() takes jobs list (dicts with 'id', 'profit', 'deadline' keys) and max_deadline. Returns dict with total profit and schedule. Docstring describes greedy profit maximization strategy.

2. Sorting by Profit (line 3): sorted() with lambda key=lambda x: x['profit'], reverse=True sorts jobs descending by profit. Lambdas extract field for comparison. Timsort O(n log n). Ensures highest-profit jobs considered first.

3. Slot Array (lines 4-5): slot = [None] * max_deadline creates list of None values (empty). List index represents time slot (0 to max_deadline-1). profit accumulator starts 0, incremented when job scheduled.

4. Greedy Loop (lines 7-13): For each job in profit order: use range(deadline-1, -1, -1) to iterate backward from (deadline-1) to 0. Check if slot[j] is None (empty). If yes, assign job['id'] to slot, add job['profit'], break. Backward iteration ensures latest slot used, maximizing availability for remaining jobs. If no empty slot, skip job.

5. Time Complexity O(n² + n log n): sorted() is O(n log n) with Timsort. Nested loops: for each job iterate backward through up to max_deadline slots, worst O(n × max_deadline) = O(n²). Total: O(n log n + n²) ≈ O(n²). Space O(max_deadline) for slot list. Same asymptotic as C but more Pythonic (dicts, lambdas, list operations).