Maximum Profit in Job Scheduling

This problem hands you jobs with start times, end times, and money. You want the most money. The catch is jobs can overlap, and you cannot do two jobs at once. Plain greedy fails here, because a job that pays a lot might block two smaller jobs that together pay even more. The clean fix sorts by end time and uses dynamic programming with binary search. That combination is the real test.

🎯 The Problem

You get jobs, and you want the most money. Here are the rules.

• Three lists of the same length: start times, end times, and profit per job.
• You may do two jobs only if they do not overlap in time.
• A job ending at time t and a job starting at time t do not overlap. So both fit.
• You want the largest total profit.

Take this set. Job A runs 1 to 3 and pays 50. Job B runs 2 to 4 and pays 10. Job C runs 3 to 5 and pays 40. Job D runs 3 to 6 and pays 70. The best choice is A then D. That gives 50 plus 70, which is 120.

Input:  startTime = [1, 2, 3, 3]
        endTime   = [3, 4, 5, 6]
        profit    = [50, 10, 40, 70]
Output: 120

Explanation: do job [1,3] for 50, then job [3,6] for 70.
The 3 == 3 boundary does not overlap, so both fit. 50 + 70 = 120.

The trap is overlap. Overlap means two jobs share time. A high-paying job is not always worth it if it blocks better combinations.

The picture below lays the four jobs on a time line.

🐢 Approach 1: Take or Skip Recursion (Brute Force)

The idea in one line: for every job, try taking it and try skipping it.

The idea:

• Each job has two choices. Take it or skip it.
• If you take it, jump past every job that overlaps it.
• If you skip it, move on to the next job.

How it works:

• Explore all paths. Keep the best total profit.
• It does give the right answer.

Why it is weak:

• Each job doubles the number of paths.
• With n jobs you get about 2 to the power n paths.
• This is exponential time. It crashes once n grows.

Here is the plain take-or-skip recursion:

def job_scheduling(start_time, end_time, profit):
    jobs = sorted(zip(start_time, end_time, profit))

    def dfs(index):
        if index == len(jobs):
            return 0
        next_index = index + 1
        while next_index < len(jobs) and jobs[next_index][0] < jobs[index][1]:
            next_index += 1
        take = jobs[index][2] + dfs(next_index)
        skip = dfs(index + 1)
        return max(take, skip)

    return dfs(0)

🐌 Approach 2: Recursion Plus Memory (Better)

The idea in one line: same take-or-skip search, but remember answers you already computed.

The idea:

• Sort jobs by start time.
• Solve “best profit from job i onward” once, then store it.
• Next time you reach job i, read the stored answer.

How it works:

• Storing and reusing answers is called memoization.
• Each job is solved one time, not over and over.

Why it is better:

• It removes the repeated work that made brute force explode.
• The time drops to O(n log n), with a binary search to skip overlapping jobs.
• But the recursion stack can grow deep. The bottom-up table is cleaner.

Here is the memoized recursion:

from functools import lru_cache


def job_scheduling(start_time, end_time, profit):
    jobs = sorted(zip(start_time, end_time, profit))

    @lru_cache(None)
    def dfs(index):
        if index == len(jobs):
            return 0
        next_index = index + 1
        while next_index < len(jobs) and jobs[next_index][0] < jobs[index][1]:
            next_index += 1
        return max(jobs[index][2] + dfs(next_index), dfs(index + 1))

    return dfs(0)

⚡ Approach 3: Sort by End Time, DP With Binary Search (Best)

The idea in one line: sort by end time, then build the best profit up job by job from the bottom.

The idea:

• Sort the jobs by their end time.
• Build the best profit using only the first few jobs. Grow it one job at a time.
• This bottom-up table is dynamic programming. You solve small pieces, save them, and reuse them.

The take-or-skip rule:

• Skip job i: your best is whatever you had before job i.
• Take job i: earn its profit, plus the best profit from jobs ending before job i starts.
• So you need the latest job that finishes in time.

How binary search helps:

• Binary search finds a value in a sorted list fast by halving the range each step.
• Jobs are sorted by end time, so binary search finds the last job ending at or before the current start.

How it works:

• Keep a table where dp[i] is the best profit using the first i jobs.
• For each job, compute take and skip. Store the larger.
• The final entry is the answer.

Why it is fast:

• Sort is O(n log n). Each job does one O(log n) binary search.
• So the whole run is O(n log n).

The diagram below shows the take-or-skip decision for one job.

Steps to Solve

1. Combine each job’s start, end, and profit into one item.
2. Sort the items by end time.
3. Keep a table dp where dp[i] is the best profit using the first i jobs. Start dp[0] at zero.
4. For each job, compute “skip”, which is dp[i-1].
5. Compute “take”, which is this job’s profit plus the best profit from jobs ending at or before this job’s start. Use binary search to find that earlier job.
6. Set dp[i] to the larger of skip and take.
7. The last entry of dp is the maximum profit.

#include <stdio.h>
#include <stdlib.h>

typedef struct { int start, end, profit; } Job;

int cmpEnd(const void *a, const void *b) {
    return ((Job *)a)->end - ((Job *)b)->end;  // sort by end time
}

int jobScheduling(int *startTime, int *endTime, int *profit, int n) {
    Job *jobs = malloc(n * sizeof(Job));
    for (int i = 0; i < n; i++) {
        jobs[i].start = startTime[i];
        jobs[i].end = endTime[i];
        jobs[i].profit = profit[i];
    }
    qsort(jobs, n, sizeof(Job), cmpEnd);

    int *dp = malloc((n + 1) * sizeof(int));
    dp[0] = 0;  // best profit using zero jobs
    for (int i = 1; i <= n; i++) {
        int skip = dp[i - 1];
        // binary search: last job (1-based) whose end <= jobs[i-1].start
        int lo = 0, hi = i - 1, idx = 0;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (mid == 0) { lo = mid + 1; continue; }
            if (jobs[mid - 1].end <= jobs[i - 1].start) { idx = mid; lo = mid + 1; }
            else hi = mid - 1;
        }
        int take = jobs[i - 1].profit + dp[idx];
        dp[i] = skip > take ? skip : take;
    }
    int ans = dp[n];
    free(jobs);
    free(dp);
    return ans;
}

int main(void) {
    int startTime[] = {1, 2, 3, 3};
    int endTime[]   = {3, 4, 5, 6};
    int profit[]    = {50, 10, 40, 70};
    printf("%d\n", jobScheduling(startTime, endTime, profit, 4));  // 120
    return 0;
}

120

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int jobScheduling(vector<int> &startTime, vector<int> &endTime, vector<int> &profit) {
    int n = startTime.size();
    vector<array<int,3>> jobs(n);  // {end, start, profit}
    for (int i = 0; i < n; i++) jobs[i] = {endTime[i], startTime[i], profit[i]};
    sort(jobs.begin(), jobs.end());  // sort by end time (first field)

    vector<int> ends(n), dp(n + 1, 0);
    for (int i = 0; i < n; i++) ends[i] = jobs[i][0];

    for (int i = 1; i <= n; i++) {
        int skip = dp[i - 1];
        int start = jobs[i - 1][1];
        // last job whose end <= start: count of ends <= start
        int idx = upper_bound(ends.begin(), ends.begin() + i, start) - ends.begin();
        int take = jobs[i - 1][2] + dp[idx];
        dp[i] = max(skip, take);
    }
    return dp[n];
}

int main() {
    vector<int> startTime = {1, 2, 3, 3};
    vector<int> endTime   = {3, 4, 5, 6};
    vector<int> profit    = {50, 10, 40, 70};
    cout << jobScheduling(startTime, endTime, profit) << endl;  // 120
    return 0;
}

120

import java.util.*;

public class JobScheduling {
    public static int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        int[][] jobs = new int[n][3];   // {end, start, profit}
        for (int i = 0; i < n; i++) jobs[i] = new int[]{endTime[i], startTime[i], profit[i]};
        Arrays.sort(jobs, (a, b) -> a[0] - b[0]);  // by end time

        int[] dp = new int[n + 1];      // dp[i] = best profit using first i jobs
        for (int i = 1; i <= n; i++) {
            int skip = dp[i - 1];
            int start = jobs[i - 1][1];
            // binary search: count of jobs (within first i) whose end <= start
            int lo = 0, hi = i - 1, idx = 0;
            while (lo < hi) {
                int mid = (lo + hi) / 2;
                if (jobs[mid][0] <= start) lo = mid + 1;
                else hi = mid;
            }
            // lo is the first index with end > start, so lo jobs are compatible
            idx = (jobs[lo][0] <= start) ? lo + 1 : lo;
            int take = jobs[i - 1][2] + dp[idx];
            dp[i] = Math.max(skip, take);
        }
        return dp[n];
    }

    public static void main(String[] args) {
        int[] startTime = {1, 2, 3, 3};
        int[] endTime   = {3, 4, 5, 6};
        int[] profit    = {50, 10, 40, 70};
        System.out.println(jobScheduling(startTime, endTime, profit));  // 120
    }
}

120

from bisect import bisect_right


def job_scheduling(start_time, end_time, profit):
    # build (end, start, profit) and sort by end time
    jobs = sorted(zip(end_time, start_time, profit))
    ends = [job[0] for job in jobs]   # sorted end times

    dp = [0] * (len(jobs) + 1)        # dp[i] = best profit using first i jobs
    for i in range(1, len(jobs) + 1):
        end, start, pay = jobs[i - 1]
        skip = dp[i - 1]                       # do not take this job
        idx = bisect_right(ends, start, 0, i)  # last job ending <= start
        take = pay + dp[idx]                   # take this job
        dp[i] = max(skip, take)                # keep the better choice
    return dp[len(jobs)]


start_time = [1, 2, 3, 3]
end_time = [3, 4, 5, 6]
profit = [50, 10, 40, 70]
print(job_scheduling(start_time, end_time, profit))  # 120

120

function jobScheduling(startTime, endTime, profit) {
  const n = startTime.length;
  // build [end, start, profit] and sort by end time
  const jobs = [];
  for (let i = 0; i < n; i++) jobs.push([endTime[i], startTime[i], profit[i]]);
  jobs.sort((a, b) => a[0] - b[0]);
  const ends = jobs.map((j) => j[0]); // sorted end times

  const dp = new Array(n + 1).fill(0); // dp[i] = best profit using first i jobs
  for (let i = 1; i <= n; i++) {
    const [end, start, pay] = jobs[i - 1];
    const skip = dp[i - 1];
    // binary search: count of jobs (within first i) with end <= start
    let lo = 0, hi = i;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (ends[mid] <= start) lo = mid + 1;
      else hi = mid;
    }
    const take = pay + dp[lo];
    dp[i] = Math.max(skip, take);
  }
  return dp[n];
}

const startTime = [1, 2, 3, 3];
const endTime = [3, 4, 5, 6];
const profit = [50, 10, 40, 70];
console.log(jobScheduling(startTime, endTime, profit)); // 120

120

Let us walk through the Python version line by line, because the dp plus binary search is the part interviewers probe.

The line jobs = sorted(zip(end_time, start_time, profit)) glues each job into a tuple (end, start, profit) and sorts. Because end is first, the sort is by end time. Sorting by end is what makes the binary search work later.

The line ends = [job[0] for job in jobs] pulls out just the end times into a sorted list. We binary search this list to find compatible jobs.

The line dp = [0] * (len(jobs) + 1) makes the table. dp[i] means the best profit you can earn using only the first i jobs. We start everything at zero. dp[0] stays zero because zero jobs earn nothing.

Inside the loop, end, start, pay = jobs[i - 1] unpacks the current job. The current job is the i-th one, which sits at index i - 1.

The line skip = dp[i - 1] is the “do not take it” choice. If we skip this job, our best is whatever we had using the earlier jobs.

The line idx = bisect_right(ends, start, 0, i) is the binary search. bisect_right finds where start would slot into the sorted ends. So idx counts how many jobs end at or before this job’s start. Those are exactly the jobs that do not overlap. So dp[idx] is the best profit we can keep alongside this job.

The line take = pay + dp[idx] is the “take it” choice. We earn this job’s pay, plus the best from compatible earlier jobs.

The line dp[i] = max(skip, take) keeps the better of the two. After the loop, the last entry holds the answer.

⏱️ Time and Space Complexity

The brute force branches on every job, so it is exponential. The dp version sorts once, which is O(n log n). Then for each of the n jobs it does one binary search, which is O(log n). So the dp loop is also O(n log n). The total stays O(n log n). The space is O(n) for the sorted jobs and the dp table.

🧩 Key Takeaways

• ✅ Sort jobs by end time so binary search can find compatible jobs fast.
• ✅ For each job choose the better of skip and take.
• ✅ Take means this job’s profit plus the best profit from jobs ending before it starts.
• ✅ Binary search finds that earlier compatible job in O(log n).
• ✅ Plain greedy by profit is wrong, because a big job can block better combinations.

🚀 What’s Next?

• Maximum Number of Events That Can Be Attended
• Design Twitter