AlgoViz
HomeGreedy

Job sequencing Problem

Medium

Highest profit first, latest free slot

Problem

Each job has a deadline and a profit and takes one unit of time. Schedule jobs to maximize total profit; each job must finish by its deadline.

In simple words

Sort by profit, then place each job in the latest free day before its deadline.

The idea

Sort jobs by profit descending and schedule each in the latest free slot before its deadline. Placing it as late as possible keeps the earlier slots open for jobs with tighter deadlines, which is what makes the greedy optimal.

The trick

  • Sort by profit, then fill backwards from the deadline.
  • A disjoint-set structure finds the latest free slot in near-constant time.
  • Skip a job entirely when no slot before its deadline is free.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

2
100
1
19
2
27
1
25
3
15
0
1
2
3
4
5
6
7
8
9

Step 1 of 2. Here's the example — jobs=[(2,100),(1,19),(2,27),(1,25),(3,15)] Values: 2, 100, 1, 19, 2, 27, 1, 25, 3, 15.

1/2
Optimal
timeO(n^2)spaceO(n)
1sort jobs by profit desc2for job in jobs:3  place it in the latest free slot <= its deadline4  if a slot was free: add its profit

Input

array
[2, 100, 1, 19, 2, 27, 1, 25, 3, 15]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
jobs(id,deadline,profit) = [(1,4,20),(2,1,10),(3,1,40),(4,1,30)]
Output:
[2, 60]
Explanation:
Do the most profitable jobs before their deadlines → 2 jobs, 60.

Example 2

Input:
jobs = [(1,2,100),(2,1,19),(3,2,27),(4,1,25),(5,1,15)]
Output:
[2, 127]
Explanation:
Best two jobs → profit 127.

Example 3

Input:
jobs = [(1,1,50)]
Output:
[1, 50]
Explanation:
One job → 1 job, 50.

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.