GeeksforGeeks Hard

Job Sequencing Problem

Each job takes 1 unit of time, has a deadline and a profit. Maximize profit by scheduling at most one job per slot, each before its deadline.

greedysortingscheduling

Open on GeeksforGeeks ↗

02

Intuition

💡

Take jobs in profit order — but place each as late as its deadline allows. Placing late keeps earlier slots free for jobs with tighter deadlines, so a rich job never squeezes out another it didn't have to.

03

Approach

1

Sort by profit, descending

If a job can be scheduled at all, we'd rather it be a high-profit one — commit to the richest first.

2

Place each in its latest free slot

For a job with deadline d, scan slots d, d−1, … 1 for a free one. Late placement preserves options for tighter jobs.

3

Optional speed-up

The slot scan can use a union-find 'next free slot' structure to reach O(n log n); the simple scan is O(n·maxD).

04

Solution & live demo

python

▶1def job_sequencing(jobs):        # jobs: [(id, deadline, profit)]
▶2    jobs.sort(key=lambda j: -j[2])
▶3    max_d = max(j[1] for j in jobs)
▶4    slot = [None] * (max_d + 1)  # slot[t] = job id, 1-indexed
▶5    count = profit = 0
▶6    for jid, d, p in jobs:
▶7        for t in range(min(d, max_d), 0, -1):
▶8            if slot[t] is None:
▶9                slot[t] = jid
▶10                count += 1; profit += p
▶11                break
▶12    return count, profit

05

Edge cases

All deadlines = 1

Only one slot exists — the single most profitable job is chosen.

More jobs than slots

Jobs failing to find a free slot are skipped, by construction the cheapest ones.

06

Complexity

Time

O(n log n + n·D)

Space

O(D)

D = max deadline; union-find drops the second term.