Job Sequencing Problem

Q: What is the time complexity of the job sequencing problem?

With a disjoint set it is O(n log n) time, dominated by the sort, and O(n) space. Scanning back from each deadline for a free slot costs O(n²) when most deadlines are large.

MediumGreedy Sorting

+10

You get n jobs as two arrays: job i earns profit[i] if it finishes by time deadline[i]. Each job takes one unit of time, you run one job at a time starting at time 0, and you may skip any job. A job with deadline 2 can run from 0 to 1 or from 1 to 2.

Return the largest total profit you can earn.

Function

jobSequencing(deadline: integer-array, profit: integer-array) → integer

deadlineinteger-array: the time by which each job has to be finished, from 1 to n
profitinteger-array: what each job earns; profit[i] belongs to deadline[i]
Returnsinteger: the largest total profit of jobs that can all finish by their deadlines

Constraints

1 ≤ deadline.length == profit.length ≤ 5000
1 ≤ deadline[i] ≤ n, where n is the number of jobs
1 ≤ profit[i] ≤ 10⁵
The arrays are not sorted. Several jobs may share a deadline or a profit.

Examples

Input: deadline = [3, 1, 2, 3, 1]profit = [40, 35, 30, 25, 50]
Output: 120
Explanation: Only one of the two deadline-1 jobs fits, so run the one worth 50. The job worth 30 then finishes at its deadline 2 and the job worth 40 at its deadline 3: 50 + 30 + 40 = 120.

Input: deadline = [1, 1, 1]profit = [5, 9, 7]
Output: 9
Explanation: All three jobs have to finish by time 1, and only one job fits before then. The best of them earns 9.

Follow-up

What if job i takes duration[i] units of time instead of one? Does taking the most profitable job first still give the best total?

Solution

You choose which jobs to keep and when to run them. One greedy rule settles both: take the jobs from the most profitable down and put each in the latest free slot at or before its deadline, skipping it when none is free. A disjoint set finds that slot without walking past booked ones.

Greedy by profit, scanning for a free slot

Intuition

Cut time into slots: slot t runs from t-1 to t, a job with deadline d may use slots 1 to d, and no deadline exceeds n. Taking the most profitable job first is safe: if every slot it could use is booked, swapping it for the job in one of them earns at least as much. Booking the latest slot is safe because early slots are the only ones short-deadline jobs can use.

The cost is the scan. When every deadline is n, the k-th job walks past k-1 booked slots: about n²/2, or 12.5 million steps at n = 5000.

Algorithm

Sort the jobs by profit, largest first, keeping each deadline with its profit.
Make an array taken of n + 1 flags, all false.
For each job, walk t down from its deadline to 1 and stop at the first slot that is not taken.
If you found one, mark it taken and add the job's profit to total.
Return total.

def jobSequencing(deadline, profit):
    n = len(deadline)
    taken = [False] * (n + 1)  # taken[t]: the time unit from t-1 to t is booked
    total = 0
    for i in sorted(range(n), key=lambda i: profit[i], reverse=True):  # most profitable first
        for t in range(deadline[i], 0, -1):  # latest free slot first
            if not taken[t]:
                taken[t] = True
                total += profit[i]
                break
    return total

Greedy by profit with a disjoint set of free slots

Intuition

The scan walks over the same booked slots again and again. A disjoint set over slots 0 to n skips them: parent[t] = t while slot t is free, and booking it sets parent[t] = t-1, so following pointers from a deadline lands on the latest free slot. Reaching slot 0 means nothing is left. Path halving points each slot you pass two steps ahead, so later walks are shorter.

In the third example, the jobs worth 60 and 50 book slots 2 and 1. The job worth 20, deadline 2, follows 2 to 1 to 0 and is skipped.

Sorting costs O(n log n), and with path halving each lookup costs O(log n) amortized, so the total stays O(n log n).

Algorithm

Sort the jobs by profit, largest first, keeping each deadline with its profit.
Set parent[t] = t for every slot t from 0 to n.
For each job, start at slot = deadline and follow parent until parent[slot] == slot, halving the path as you go.
If slot > 0, add the job's profit and set parent[slot] = slot-1; otherwise skip the job.
Return the total.

def jobSequencing(deadline, profit):
    n = len(deadline)
    # following parent from slot t ends at the latest free slot at or before t; 0 means none is left
    parent = list(range(n + 1))
    total = 0
    for i in sorted(range(n), key=lambda i: profit[i], reverse=True):  # most profitable first
        slot = deadline[i]
        while parent[slot] != slot:
            parent[slot] = parent[parent[slot]]  # halve the path as you go
            slot = parent[slot]
        if slot > 0:
            total += profit[i]
            parent[slot] = slot - 1  # booked: its chain continues at the slot before it
    return total

Pitfalls and edge cases

Putting a job in the earliest free slot. In the third example the job worth 60 would take slot 1, and the job worth 50 would be lost: 80 instead of 110.
Taking jobs in order of deadline. With deadlines [1, 1] and profits [1, 100], the cheap job takes the only slot and you earn 1 instead of 100.
Sizing the slot array n instead of n + 1. A deadline equal to n then reads past the end.
Sorting the profits on their own. Each deadline has to move with its profit.
Writing the find step with recursion. A chain through thousands of booked slots can overflow the stack; use a loop.

Frequently asked questions3

What is the time complexity of the job sequencing problem?

With a disjoint set it is O(n log n) time, dominated by the sort, and O(n) space. Scanning back from each deadline for a free slot costs O(n²) when most deadlines are large.

Why does the greedy approach work for job sequencing?

Some best schedule contains the most profitable job. If it is left out and a slot before its deadline is free, adding it earns more; if every such slot is booked, swapping it in earns at least as much. The argument repeats for the remaining jobs.

Can job sequencing be solved with a heap instead?

Yes. Sort the jobs by deadline and push each profit into a min-heap. Whenever the heap holds more jobs than the current deadline allows, pop the smallest profit. At the end the heap holds the best set of jobs, and its sum is the answer, in O(n log n).

def jobSequencing(deadline, profit):
    # Write code here

Test #1

Test #2

Test #3

Arguments

deadline = [3, 1, 2, 3, 1]
profit = [40, 35, 30, 25, 50]

Expected Output