How to sequence jobs for max profit?

Sort jobs by descending profit and try to schedule each job as late as possible before its deadline to save earlier slots.

Why schedule "as late as possible"?

This Greedy logic preserves early time slots for jobs with tighter deadlines, allowing for a more flexible and higher-profit schedule.

Complexity of Job Sequencing?

O(n²) in the basic version, but can be optimized to O(n log n) using Disjoint Set Union (DSU) to find available slots quickly.

Job Sequencing with Deadlines

The Job Sequencing with Deadlines problem asks which jobs to schedule, each with a deadline and a profit and each taking one unit of time, to maximize the total profit.

Sorting by profit is the half everyone remembers. The half that decides the answer is which free slot a job takes once it has been picked — so change the slot rule and watch the profit fall.

READY

100

Profit

5 jobs, one machine, one time unit each. A job pays only if it runs at or before its deadline.

Sort by profit, highest first. The richest job picks its slot before any cheaper job gets a say.

Take

Intuition

If you want to make the most money, you should naturally try to do the highest-paying jobs first. However, every job has a deadline.

To maximize your chance of fitting in other high-paying jobs later, you should delay doing a job until the last possible moment before its deadline. This greedy choice leaves earlier time slots open for jobs that must be done sooner.

Concept

The Greedy Strategy:

Sort all jobs in decreasing order of profit.
Iterate through the sorted jobs. For each job, try to schedule it in the latest possible free time slot that is before its deadline.
If a slot is found, mark it as occupied and add the job's profit to the total.

How it Works

Sort: Sort jobs by Profit (high to low).
Initialize: Create a timeline (array) of size equal to the maximum deadline. Initialize all slots as free.
Iterate: For every job J with deadline D:
- Check slots from min(D, max_time) down to 1.
- If slot t is free, assign J to slot t.
- Mark slot t occupied.
- Add profit.

Step-by-Step Breakdown

Jobs: J1(D:2, P:100), J2(D:1, P:19), J3(D:2, P:27), J4(D:1, P:25), J5(D:3, P:15)

Sort: J1(100), J3(27), J4(25), J2(19), J5(15).
J1 (D:2): Try slot 2. Free? Yes. Assign J1 to [1-2]. Profit=100.
J3 (D:2): Try slot 2. Occupied. Try slot 1. Free? Yes. Assign J3 to [0-1]. Profit=127.
J4 (D:1): Try slot 1. Occupied. No slots left < 1. Skip.
J2 (D:1): Try slot 1. Occupied. Skip.
J5 (D:3): Try slot 3. Free? Yes. Assign J5 to [2-3]. Profit=142.
Total Profit: 142.

When to Use

Maximizing profit from tasks with deadlines.
Resource scheduling where tasks consume fixed unit time.

When NOT to Use

When tasks have different durations (requires DP or different greedy).
When tasks have release times.

How to Identify

Keywords: "Maximize profit", "Deadlines", "Unit time jobs".

Sample Problems

Job Sequencing Problem

Standard implementation.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description

Interval Scheduling

Minimum Platforms

Complexity

Time (Best)

Ω(N log N)

Time (Average)

Θ(N log N + N*D)

Time (Worst)

O(N log N + N*D)

Space

O(D)

Job Sequencing with Deadlines Code

1function jobSequencing(jobs) {
2    // jobs: {id, deadline, profit}[]
3    // Sort desc by profit
4    jobs.sort((a, b) => b.profit - a.profit);
5    
6    let maxDeadline = 0;
7    for(let j of jobs) maxDeadline = Math.max(maxDeadline, j.deadline);
8    
9    const slots = new Array(maxDeadline + 1).fill(-1);
10    let count = 0, totalProfit = 0;
11    
12    for(let job of jobs) {
13        // Find free slot
14        for(let j = job.deadline; j > 0; j--) {
15            if(slots[j] === -1) {
16                slots[j] = job.id;
17                count++;
18                totalProfit += job.profit;
19                break;
20            }
21        }
22    }
23    return [count, totalProfit];
24}

Related Lessons