AlgoMaster Logo

Maximum Profit in Job Scheduling

hardFrequency8 min readUpdated June 23, 2026

Understanding the Problem

We have a set of jobs, each with a start time, end time, and profit. We want to select a subset of non-overlapping jobs that maximizes total profit. Two jobs overlap if one starts before the other ends (but a job ending at time X does not overlap with a job starting at time X).

This is a weighted job scheduling problem. What makes it harder than the unweighted version (where you maximize the count of non-overlapping intervals) is that each job has a different profit. A greedy choice of the shortest or earliest-ending jobs can fail, since a single high-profit job might be worth more than several low-profit ones that fit in the same time window.

For each job, there are exactly two choices: take it and earn its profit (after which you can only take jobs that do not overlap with it), or skip it. That binary choice over a sequence with overlapping subproblems is what makes dynamic programming the fit here.

Key Constraints:

  • n <= 5 * 10^4 --> An O(n^2) solution is about 2.5 billion operations, too slow. The target is O(n log n).
  • startTime[i], endTime[i] <= 10^9 --> Times are too large to index into a time-keyed DP array. The DP must be over job indices, not time values.
  • profit[i] <= 10^4 --> Profits are positive, so taking a job never lowers the total on its own. A job is only worth skipping when it conflicts with a more profitable combination. With at most 5 10^4 jobs each under 10^4, the total fits in a 32-bit signed int (max around 5 10^8), so int does not overflow.

Approach 1: Brute Force (Recursion)

Intuition

Consider every possible subset of non-overlapping jobs and pick the one with the highest total profit. For each job, decide to take it or skip it. Taking it means moving ahead to the next job that does not overlap. Skipping it means moving to the next job.

Sort the jobs by start time so the recursion can process them left to right. Define a recursive function starting from job 0: either include the current job and move to the next non-conflicting one, or skip it and move to the next job.

Algorithm

  1. Combine start times, end times, and profits into a list of jobs. Sort by start time.
  2. Define solve(i) that returns the maximum profit from jobs i through n-1.
  3. Base case: if i >= n, return 0.
  4. Skip job i: solve(i + 1).
  5. Take job i: profit[i] + solve(next) where next is the first job whose start time >= end time of job i. Find next by linearly scanning from i + 1.
  6. Return the maximum of skip and take.

Example Walkthrough

1solve(0): Job [1,3] p=50. Take or skip?
[1, 3]
[2, 4]
[3, 5]
[3, 6]
16
1/4

Code

The recursion recomputes the same solve(i) calls many times, and the linear scan for the next job is itself O(n). The next approach caches each result and replaces the scan with binary search.

Approach 2: DP with Memoization + Binary Search

Intuition

Memoization caches the result of solve(i) the first time and returns it on later calls, so each subproblem is computed once. That alone is not enough: finding the next non-overlapping job with a linear scan still costs O(n) per job, leaving the overall solution at O(n^2).

The fix for the scan comes from the sort order. With jobs sorted by start time, the end time of job i is a threshold, and we want the first job whose start time is at or after that threshold. Searching for the leftmost qualifying position in a sorted array is a binary search, which drops the per-job lookup from O(n) to O(log n).

Algorithm

  1. Combine and sort jobs by start time.
  2. Define solve(i) with memoization: the maximum profit from jobs i through n-1.
  3. Base case: if i >= n, return 0.
  4. Skip: solve(i + 1).
  5. Take: Use binary search on start times to find the first job whose start time >= end time of job i. Then profit[i] + solve(next).
  6. Return max(skip, take).

Example Walkthrough

jobs (sorted by start time)
1solve(0): Job [1,3] p=50. Skip or take?
[1, 3]
[2, 4]
[3, 5]
[3, 6]
16
memo
1Initialize memo: all -1 (uncomputed)
0
-1
1
-1
2
-1
3
-1
1/6

Code

The memoized approach is already O(n log n). The next approach expresses the same recurrence iteratively, filling a DP table from left to right with no recursion stack.

Approach 3: Bottom-Up DP + Binary Search (Optimal)

Intuition

Approach 2 is already O(n log n). Bottom-up DP expresses the same recurrence iteratively, which removes the recursion stack.

Sort jobs by end time. (Either sort order works; end time is the standard formulation for this problem and makes the lookup a search over end times.) Define dp[i] as the maximum profit considering only the first i jobs after sorting. For each job i, there are two choices:

  • Skip job i: The best profit is whatever the first i-1 jobs achieved, which is dp[i-1].
  • Take job i: Earn profit[i] plus the best profit from all jobs that finish at or before job i starts. That means the largest j with endTime[j] <= startTime[i]. Since jobs are sorted by end time, this is a binary search.

So dp[i] = max(dp[i-1], profit[i] + dp[j]) where j is found via binary search.

Algorithm

  1. Combine jobs into tuples and sort by end time.
  2. Create a dp array of size n + 1, where dp[0] = 0 (no jobs, no profit).
  3. For each job i (1-indexed after sorting), binary search for the latest job j whose end time <= start time of job i.
  4. dp[i] = max(dp[i-1], profit[i] + dp[j]).
  5. Return dp[n].

Example Walkthrough

jobs (sorted by end time)
1Jobs sorted by end time. dp[0]=0 (no jobs).
[1, 3]
[2, 4]
[3, 5]
[3, 6]
16
dp
1Initialize dp[0]=0 (no jobs, no profit)
0
0
base
1
0
2
0
3
0
4
0
1/6

Code