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

Given a set of jobs where each job has a deadline and a profit associated with it. Each job takes a single unit of time to complete and the task is to complete as many jobs as possible to maximize the total profit.

Job Sequencing

Ready

See the Logic in Motion

Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.

Unlock VisualizerPREMIUM FEATURE

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".

Stop Guessing, Start Mastering.

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.

Start Your Premium Prep