Job Sequencing Problem

MediumProblemExternal linkUpdated Sep 27, 2026

Description

You have n jobs. Job i has a deadline, deadline[i], and a profit, profit[i].

Every job takes exactly one day, and only one job can be done per day. Days are numbered 1, 2, 3, and so on.
A job earns its profit only if it is done on or before its deadline. A job with deadline 3 can be done on day 1, 2 or 3.
You do not have to do every job.

Return [count, total]: the number of jobs in the most profitable schedule, and the profit that schedule earns.

Every profit is positive, so all of the most profitable schedules do the same number of jobs, and the count is always well defined.

Examples

Example 1

Input: deadline = [2, 1, 3, 1, 3], profit = [50, 40, 30, 10, 20]

Output: [3, 120]

Explanation:

Day 1: job 1 (deadline 1, profit 40)
Day 2: job 0 (deadline 2, profit 50)
Day 3: job 2 (deadline 3, profit 30)

That is 3 jobs for 40 + 50 + 30 = 120. Job 3 (deadline 1) and job 4 (deadline 3) do not fit, because every day up to their deadlines is already used by a more profitable job.

Notice where job 0 goes. Putting it on day 1, the first free day, would leave job 1 (deadline 1) with nowhere to go, and the greedy's total would drop to 100.

Example 2

Input: deadline = [1, 1, 1], profit = [5, 9, 7]

Output: [1, 9]

Explanation: Every job must be done on day 1, and only one job fits in a day. The best choice is the job worth 9.

Example 3

Input: deadline = [4, 4, 4], profit = [10, 20, 30]

Output: [3, 60]

Explanation: The shared deadline leaves 4 days and there are only 3 jobs, so all of them fit, on days 1, 2 and 3 in any order: 10 + 20 + 30 = 60.

Constraints

1 ≤ n ≤ 10^5, where n = deadline.length = profit.length
1 ≤ deadline[i] ≤ n
1 ≤ profit[i] ≤ 500

Editorial

Brute Force

Intuition

The real question is which jobs to do. Once a set of jobs is chosen, arranging them is easy: do them in order of deadline, the most urgent first, one per day. If any order works, this one does too: moving a more urgent job ahead of a less urgent one keeps both on time, because the less urgent job takes over a day the urgent one could use, and its own deadline is at least as late.

That gives a simple test for any set: sort its deadlines, and the k-th smallest must be at least k, since the k-th job in that order is done on day k. For example, deadlines {1, 1} fail, because the second job would need day 2, while {1, 2, 3} pass.

So the brute force tries every set of jobs, keeps the ones that pass the test, and remembers the most profitable. It does this by deciding job by job: leave it out, or take it.

Step-by-Step Explanation

Example 1, deadline = [2, 1, 3, 1, 3], profit = [50, 40, 30, 10, 20]. With 5 jobs there are 2^5 = 32 sets to try. Here are seven of them, chosen to show every kind of result.

Step 1: Start with no best yet (0 jobs, 0 profit).

Step 2: {job 0}: deadlines [2]. One job on day 1 is fine, so it passes. Profit 50, the new best.

Step 3: {job 0, job 1}: sorted deadlines [1, 2]. Day 1 ≤ 1 and day 2 ≤ 2, so it passes. Profit 90, the new best.

Step 4: {job 1, job 3}: sorted deadlines [1, 1]. The second job would be done on day 2, after its deadline of 1, so it fails.

Step 5: {job 0, job 1, job 2}: sorted deadlines [1, 2, 3]. Every job fits, so it passes. Profit 120, the new best.

Step 6: {job 0, job 1, job 2, job 4}: sorted deadlines [1, 2, 3, 3]. The fourth job would need day 4 but its deadline is 3, so it fails. Four jobs can never fit here, because no deadline is later than day 3.

Step 7: {job 0, job 2, job 4}: sorted deadlines [2, 3, 3]. It passes, but its profit of 100 is below 120.

Step 8: {job 1, job 2, job 4}: sorted deadlines [1, 3, 3]. It passes, with profit 90.

Step 9: After all 32 sets, the best is {job 0, job 1, job 2}: [3, 120].

Brute Force: Trying Every Set of Jobs — Each set is tested by sorting its deadlines; the k-th must be at least k. Green sets fit and set a new best, blue sets fit but earn less, orange sets do not fit.

Algorithm

Define explore(i), which decides for jobs i to n − 1:
- If i == n, test the chosen set: sort its deadlines and check that the k-th smallest is at least k. If it passes and its profit beats the best, remember its size and profit.
- Otherwise, call explore(i + 1) without job i, then add job i and call explore(i + 1) again.
Call explore(0) and return [best count, best profit].

Code

class Solution {
public:
    vector<int> jobSequencing(vector<int>& deadline, vector<int>& profit) {
        explore(0, deadline, profit);
        return {bestCount, bestTotal};
    }

private:
    vector<int> chosen;
    int bestCount = 0, bestTotal = 0;

    void explore(int i, vector<int>& deadline, vector<int>& profit) {
        if (i == (int)deadline.size()) {
            int total = 0;
            for (int j : chosen) total += profit[j];
            if (total > bestTotal && doable(deadline)) {
                bestCount = chosen.size();
                bestTotal = total;
            }
            return;
        }
        explore(i + 1, deadline, profit);  // leave job i out
        chosen.push_back(i);               // take job i
        explore(i + 1, deadline, profit);
        chosen.pop_back();
    }

    // Earliest deadline first: the k-th job must have a deadline of at least k
    bool doable(vector<int>& deadline) {
        vector<int> days;
        for (int j : chosen) days.push_back(deadline[j]);
        sort(days.begin(), days.end());
        for (int k = 1; k <= (int)days.size(); k++) {
            if (days[k - 1] < k) return false;
        }
        return true;
    }
};

import sys
from typing import List

class Solution:
    def jobSequencing(self, deadline: List[int], profit: List[int]) -> List[int]:
        n = len(deadline)
        sys.setrecursionlimit(max(1000, n + 100))  # one level per job
        best = [0, 0]  # [count, total] of the best doable set found so far
        chosen = []

        def doable() -> bool:
            # Earliest deadline first: the k-th job must have a deadline of at least k
            days = sorted(deadline[j] for j in chosen)
            return all(d >= k for k, d in enumerate(days, 1))

        def explore(i: int) -> None:
            if i == n:
                total = sum(profit[j] for j in chosen)
                if total > best[1] and doable():
                    best[0], best[1] = len(chosen), total
                return
            explore(i + 1)    # leave job i out
            chosen.append(i)  # take job i
            explore(i + 1)
            chosen.pop()

        explore(0)
        return best

import java.util.*;

class Solution {
    private int[] deadline, profit;
    private final List<Integer> chosen = new ArrayList<>();
    private int bestCount = 0, bestTotal = 0;

    public int[] jobSequencing(int[] deadline, int[] profit) {
        this.deadline = deadline;
        this.profit = profit;
        explore(0);
        return new int[]{bestCount, bestTotal};
    }

    private void explore(int i) {
        if (i == deadline.length) {
            int total = 0;
            for (int j : chosen) total += profit[j];
            if (total > bestTotal && doable()) {
                bestCount = chosen.size();
                bestTotal = total;
            }
            return;
        }
        explore(i + 1);    // leave job i out
        chosen.add(i);     // take job i
        explore(i + 1);
        chosen.remove(chosen.size() - 1);
    }

    // Earliest deadline first: the k-th job must have a deadline of at least k
    private boolean doable() {
        List<Integer> days = new ArrayList<>();
        for (int j : chosen) days.add(deadline[j]);
        Collections.sort(days);
        for (int k = 1; k <= days.size(); k++) {
            if (days.get(k - 1) < k) return false;
        }
        return true;
    }
}

Complexity Analysis

Time Complexity: O(2^n × n log n)

Every job is either in or out, so there are 2^n sets, and testing one means sorting up to n deadlines. With n = 30 that is already over a billion sets.

Space Complexity: O(n)

The chosen set and the recursion each hold at most n items.

Why This Approach Is Not Efficient

2^n sets is hopeless. n can be 100,000, and even n = 40 already means about a trillion sets.

The brute force also ignores what the problem is telling it. Two facts make most sets pointless to try:

Profit decides everything. A very profitable job should be in the schedule unless something forces it out. Trying sets that leave it out for no reason is wasted work.
Late days are the flexible ones. Every job can use day 1, but only jobs with deadline 3 or more can use day 3. So a job should take the latest day it can, and leave the early days for jobs that need them.

Together these suggest building the schedule directly, one job at a time, instead of testing sets.

Better Approach - Greedy With the Latest Free Day

Intuition

Go through the jobs from the most profitable to the least. For each one, put it on the latest free day on or before its deadline. If every such day is taken, skip the job.

Why the latest free day? Early days are the scarce ones, since every job can use them. Taking the latest possible day keeps them open for jobs with tighter deadlines. In Example 1, putting job 0 (deadline 2) on day 2 keeps day 1 free for job 1 (deadline 1).

Why is taking the most profitable job first safe? Say job J is the most profitable one left, and the greedy puts it on day t, the latest free day on or before its deadline. Take any best schedule:

If it does J on an earlier day, swap J with whatever it does on day t. That job moves earlier, which never breaks its deadline, and the profit stays the same.
If it leaves J out, put J on day t in place of whatever was there. That job is worth no more than J, so the profit does not drop.

Either way, some best schedule agrees with the greedy's choice. The same reasoning repeats for every job that follows, so the greedy's schedule is as profitable as the best one.

To find the latest free day, start at the deadline and walk back one day at a time until a free day turns up, or until day 0, which means none is left.

Step-by-Step Explanation

Example 1. In order of profit the jobs are 50 (deadline 2), 40 (deadline 1), 30 (deadline 3), 20 (deadline 3) and 10 (deadline 1). The deadlines go up to day 3, so there are 3 days to fill.

Step 1: Start with days 1 to 3 all free, and the jobs lined up by profit.

Step 2: Job 50, deadline 2. Look at day 2: it is free.

Step 3: Put job 50 on day 2. Count 1, total 50.

Step 4: Job 40, deadline 1. Look at day 1: it is free.

Step 5: Put job 40 on day 1. Count 2, total 90.

Step 6: Job 30, deadline 3. Look at day 3: it is free.

Step 7: Put job 30 on day 3. Count 3, total 120.

Step 8: Job 20, deadline 3. Day 3 is taken.

Step 9: Walk back to day 2: taken.

Step 10: Walk back to day 1: taken.

Step 11: Walk back to day 0, which means no free day is left, so skip job 20.

Step 12: Job 10, deadline 1. Day 1 is taken, and walking back reaches day 0, so skip it.

Step 13: The answer is [3, 120]. Job 20 alone needed 3 checks to find out it had no room.

Greedy: Most Profitable First, Walking Back to a Free Day — Top row: days 1 to 3 and the job done on each. Bottom row: jobs still waiting, most profitable first. The pointer shows the day being checked; green is a job just placed, orange a day already taken.

Algorithm

Let maxDay be the largest deadline, and mark days 1 to maxDay as free.
Go through the jobs in order of profit, highest first. For each job:
- Set day = deadline. While day > 0 and day is taken, decrease day.
- If day > 0, mark it taken, add 1 to the count and the job's profit to the total. Otherwise skip the job.
Return [count, total].

Code

class Solution {
public:
    vector<int> jobSequencing(vector<int>& deadline, vector<int>& profit) {
        int n = deadline.size();
        int maxDay = *max_element(deadline.begin(), deadline.end());
        vector<bool> taken(maxDay + 1, false);  // taken[d]: is day d used? (days are 1..maxDay)
        vector<int> order(n);
        iota(order.begin(), order.end(), 0);
        sort(order.begin(), order.end(), [&](int a, int b) { return profit[a] > profit[b]; });  // most profitable first

        int count = 0, total = 0;
        for (int i : order) {
            int day = deadline[i];
            while (day > 0 && taken[day]) day--;  // walk back to the latest free day
            if (day > 0) {
                taken[day] = true;
                count++;
                total += profit[i];
            }
        }
        return {count, total};
    }
};

from typing import List

class Solution:
    def jobSequencing(self, deadline: List[int], profit: List[int]) -> List[int]:
        n = len(deadline)
        taken = [False] * (max(deadline) + 1)  # taken[d]: is day d used? (days are 1..max deadline)
        count, total = 0, 0
        for i in sorted(range(n), key=lambda i: -profit[i]):  # most profitable first
            day = deadline[i]
            while day > 0 and taken[day]:  # walk back to the latest free day
                day -= 1
            if day > 0:
                taken[day] = True
                count += 1
                total += profit[i]
        return [count, total]

import java.util.*;

class Solution {
    public int[] jobSequencing(int[] deadline, int[] profit) {
        int n = deadline.length, maxDay = 0;
        for (int d : deadline) maxDay = Math.max(maxDay, d);
        boolean[] taken = new boolean[maxDay + 1];  // taken[d]: is day d used? (days are 1..maxDay)
        Integer[] order = new Integer[n];
        for (int i = 0; i < n; i++) order[i] = i;
        Arrays.sort(order, (a, b) -> profit[b] - profit[a]);  // most profitable first

        int count = 0, total = 0;
        for (int i : order) {
            int day = deadline[i];
            while (day > 0 && taken[day]) day--;  // walk back to the latest free day
            if (day > 0) {
                taken[day] = true;
                count++;
                total += profit[i];
            }
        }
        return new int[]{count, total};
    }
}

Complexity Analysis

Time Complexity: O(n log n + n × D), which is O(n²) in the worst case

Sorting by profit costs O(n log n). Each job may then walk back over up to D days, where D ≤ n is the largest deadline. The worst case is when every deadline is the last day: the k-th job walks past k − 1 taken days, about n²/2 checks in total. For n = 100,000 that is 5 × 10^9.

Space Complexity: O(n)

One flag per day, plus the order of the jobs.

Why This Approach Is Not Efficient

The greedy is right, but the walk back is slow. When days fill up from the end, every new job starts at its deadline and walks over the same taken days that the previous job just walked over. The walk forgets what it learned.

What if each day remembered where the walk would end? Let every day point to the latest free day on or before it. When a day gets taken, it simply points to the day before instead. And after each search, point every day that was passed straight at the answer, so no one walks that stretch again.

This is a disjoint set, also called union-find. It finds the latest free day in almost constant time, and brings the whole algorithm down to the cost of sorting.

Optimal Approach - Greedy With a Disjoint Set

Intuition

Keep the same greedy, most profitable first and latest free day. Only the search changes.

Keep an array slot with one entry per day, from day 0 to the largest deadline:

slot[d] = d means day d is free.
Otherwise slot[d] points to an earlier day to continue the search.
Day 0 always points to itself and stands for "no day left".

To find the latest free day on or before d, follow the pointers from d until reaching a day that points to itself. When a job takes day t, set slot[t] = t − 1, so any later search that reaches t continues at the day before.

The shortcut: after a search from d ends at day r, point every day it passed straight at r. The next search starting anywhere on that path jumps there in one step, instead of repeating the walk. This trick is called path compression.

The jobs, the order and the schedule are exactly the same as before. The only difference is that finding a free day no longer means stepping back one day at a time.

Another way to reach O(n log n): go through the jobs in order of deadline instead, keeping the profits of the jobs chosen so far in a min-heap. Whenever there are more chosen jobs than days up to the current deadline, drop the least profitable one. The heap ends up holding exactly the best schedule's jobs.

Step-by-Step Explanation

Example 1 again, with the jobs in profit order: 50 (deadline 2), 40 (deadline 1), 30 (deadline 3), 20 (deadline 3) and 10 (deadline 1).

Step 1: slot = [0, 1, 2, 3]. Every day points to itself, so every day is free.

Step 2: Job 50, deadline 2. slot[2] = 2, so day 2 is free.

Step 3: Take day 2 and set slot[2] = 1. Count 1, total 50.

Step 4: Job 40, deadline 1. slot[1] = 1, so day 1 is free.

Step 5: Take day 1 and set slot[1] = 0. Count 2, total 90.

Step 6: Job 30, deadline 3. slot[3] = 3, so day 3 is free.

Step 7: Take day 3 and set slot[3] = 2. Count 3, total 120.

Step 8: Job 20, deadline 3. Follow the pointers: 3 → 2 → 1 → 0. Day 0 points to itself, so the answer is day 0: no free day left.

Step 9: Shortcut the path: slot[3] = 0 and slot[2] = 0. Skip job 20.

Step 10: Job 10, deadline 1. slot[1] = 0, so the search ends at day 0 in one step. Skip it.

Step 11: The answer is [3, 120], the same schedule as before. After the shortcut, any later search from day 3 would finish in a single step.

Greedy With Shortcuts: Jumping Straight to a Free Day — Top row: slot[d] for each day d; a day pointing to itself is free, and day 0 means no day. Bottom row: the schedule. Highlighted cells are the search path.

Algorithm

Let maxDay be the largest deadline, and create slot[d] = d for every day d from 0 to maxDay.
Define latestFree(d):
- Follow slot from d until reaching a day r with slot[r] == r.
- Walk the path again and set each day on it to r (the shortcut).
- Return r.
Go through the jobs in order of profit, highest first. For each job, let day = latestFree(deadline). If day > 0, set slot[day] = day − 1, add 1 to the count and the profit to the total. Otherwise skip the job.
Return [count, total].

Code

class Solution {
public:
    vector<int> jobSequencing(vector<int>& deadline, vector<int>& profit) {
        int n = deadline.size();
        int maxDay = *max_element(deadline.begin(), deadline.end());
        slot.assign(maxDay + 1, 0);  // slot[d] leads to the latest free day on or before d; slot[0] = 0 means "no day left"
        iota(slot.begin(), slot.end(), 0);
        vector<int> order(n);
        iota(order.begin(), order.end(), 0);
        sort(order.begin(), order.end(), [&](int a, int b) { return profit[a] > profit[b]; });  // most profitable first

        int count = 0, total = 0;
        for (int i : order) {
            int day = latestFree(deadline[i]);
            if (day > 0) {
                slot[day] = day - 1;  // day is now used; searches from it continue at the day before
                count++;
                total += profit[i];
            }
        }
        return {count, total};
    }

private:
    vector<int> slot;

    int latestFree(int d) {
        int root = d;
        while (slot[root] != root) root = slot[root];
        while (slot[d] != root) {  // shortcut every day we passed straight to the answer
            int next = slot[d];
            slot[d] = root;
            d = next;
        }
        return root;
    }
};

from typing import List

class Solution:
    def jobSequencing(self, deadline: List[int], profit: List[int]) -> List[int]:
        n = len(deadline)
        # slot[d] leads to the latest free day on or before d; slot[0] = 0 means "no day left"
        slot = list(range(max(deadline) + 1))

        def latest_free(d: int) -> int:
            root = d
            while slot[root] != root:
                root = slot[root]
            while slot[d] != root:  # shortcut every day we passed straight to the answer
                slot[d], d = root, slot[d]
            return root

        count, total = 0, 0
        for i in sorted(range(n), key=lambda i: -profit[i]):  # most profitable first
            day = latest_free(deadline[i])
            if day > 0:
                slot[day] = day - 1  # day is now used; searches from it continue at the day before
                count += 1
                total += profit[i]
        return [count, total]

import java.util.*;

class Solution {
    private int[] slot;  // slot[d] leads to the latest free day on or before d; slot[0] = 0 means "no day left"

    public int[] jobSequencing(int[] deadline, int[] profit) {
        int n = deadline.length, maxDay = 0;
        for (int d : deadline) maxDay = Math.max(maxDay, d);
        slot = new int[maxDay + 1];
        for (int d = 0; d <= maxDay; d++) slot[d] = d;
        Integer[] order = new Integer[n];
        for (int i = 0; i < n; i++) order[i] = i;
        Arrays.sort(order, (a, b) -> profit[b] - profit[a]);  // most profitable first

        int count = 0, total = 0;
        for (int i : order) {
            int day = latestFree(deadline[i]);
            if (day > 0) {
                slot[day] = day - 1;  // day is now used; searches from it continue at the day before
                count++;
                total += profit[i];
            }
        }
        return new int[]{count, total};
    }

    private int latestFree(int d) {
        int root = d;
        while (slot[root] != root) root = slot[root];
        while (slot[d] != root) {  // shortcut every day we passed straight to the answer
            int next = slot[d];
            slot[d] = root;
            d = next;
        }
        return root;
    }
}

Complexity Analysis

Time Complexity: O(n log n)

Sorting by profit costs O(n log n). With the shortcut, a search costs O(log D) steps on average over the whole run, and close to one step in practice, since passed days jump straight to the answer. D ≤ n, so all the searches together cost no more than the sort.

Space Complexity: O(n)

The slot array has D + 1 entries, plus the order of the jobs.

Comparison:

Approach	Time	Extra space
Brute force: every set	O(2^n × n log n)	O(n)
Greedy, walking back	O(n log n + n × D), O(n²) worst case	O(n)
Greedy with shortcuts	O(n log n)	O(n)