Max Profit in Job Scheduling

Problem Statement

You are given n jobs where each job i has a startTime[i], endTime[i], and profit[i]. Find the maximum profit you can earn by scheduling non-overlapping jobs. You can start a new job at the exact time another one ends.

Example 1:

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120
Explanation: Pick job 0 (1-3, profit 50) and job 3 (3-6, profit 70). Total = 120.

Example 2:

Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
Output: 150
Explanation: Pick job 0 (1-3, profit 20), job 3 (4-6, profit 70), job 4 (6-9, profit 60). Total = 150.

Constraints:

• 1 <= n <= 5 * 10^4
• 1 <= startTime[i] < endTime[i] <= 10^9
• 1 <= profit[i] <= 10^4

Difficulty: Hard (LC 1235)

---

Pattern Recognition

• What is the input structure? A set of intervals (jobs) with associated weights (profits).
• What are we optimizing? Maximum total profit from non-overlapping intervals.
• What pattern does this fit? Weighted Job Scheduling — DP + Binary Search. Sort by end time, then for each job decide to take or skip. If you take a job, binary search for the latest non-overlapping previous job.
• Why does this pattern fit? The take/skip decision at each job creates overlapping subproblems. Sorting by end time ensures that all jobs considered before job i end before or at the same time, and binary search efficiently finds the last compatible job.

---

Approach

Brute Force — Recursion (All Subsets)

Try all 2^n subsets, check for overlaps, and return the maximum profit among valid subsets.

function maxProfit(jobs, i):
    if i >= n: return 0
    # Skip job i
    skip = maxProfit(jobs, i + 1)
    # Take job i — find next non-overlapping job
    j = first job after jobs[i] ends
    take = jobs[i].profit + maxProfit(jobs, j)
    return max(skip, take)

Time: O(2^n) without memoization. Space: O(n) recursion stack. Why insufficient: Exponential — impractical for n up to 50,000.

Optimal — DP + Binary Search

Key Insight: Sort jobs by end time. Define dp[i] as the max profit considering the first i jobs. For each job, you either skip it (profit = dp[i-1]) or take it (profit = job[i].profit + dp[last non-overlapping job]). Binary search finds the last non-overlapping job in O(log n).

Step-by-step:

1. Combine (startTime, endTime, profit) into jobs and sort by endTime.
2. Create dp array where dp[i] = max profit using the first i jobs.
3. For each job i:
   • Skip: dp[i] = dp[i-1]
   • Take: Binary search the end times for the largest index j where endTime[j] <= startTime[i]. Profit = jobs[i].profit + dp[j].
   • dp[i] = max(skip, take)
4. Return dp[n].

function jobScheduling(startTime, endTime, profit):
    jobs = zip and sort by endTime
    dp = [0] * (n + 1)
    for i in 1..n:
        j = binary search for last job ending <= jobs[i].start
        dp[i] = max(dp[i-1], jobs[i].profit + dp[j])
    return dp[n]

Time: O(n log n) — sorting + n binary searches. Space: O(n) for the DP array.

---

Walkthrough

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

Step 1 — Sort by end time (already sorted):

Index (1-based)	Start	End	Profit
1	1	3	50
2	2	4	10
3	3	5	40
4	3	6	70

End times array (for binary search): [3, 4, 5, 6]

Step 2 — Fill DP:

dp[0] = 0 (base case — no jobs)

i	Job	Start	Skip = dp[i-1]	Binary search: last end <= start	j	Take = profit + dp[j]	dp[i] = max(skip, take)
1	(1,3,50)	1	dp[0] = 0	last end <= 1 → none → j=0	0	50 + dp[0] = 50	50
2	(2,4,10)	2	dp[1] = 50	last end <= 2 → none → j=0	0	10 + dp[0] = 10	50
3	(3,5,40)	3	dp[2] = 50	last end <= 3 → job 1 (end=3) → j=1	1	40 + dp[1] = 90	90
4	(3,6,70)	3	dp[3] = 90	last end <= 3 → job 1 (end=3) → j=1	1	70 + dp[1] = 120	120

Answer: 120 — Take job 1 (profit 50) and job 4 (profit 70).

---

Implementation

TypeScript

function jobScheduling(
    startTime: number[], endTime: number[], profit: number[]
): number {
    const n = startTime.length;

    // Combine and sort by end time
    const jobs: [number, number, number][] = [];
    for (let i = 0; i < n; i++) {
        jobs.push([endTime[i], startTime[i], profit[i]]);
    }
    jobs.sort((a, b) => a[0] - b[0]);

    // Extract sorted end times for binary search
    const ends = jobs.map(j => j[0]);

    // dp[i] = max profit considering first i jobs (1-indexed)
    const dp = new Array(n + 1).fill(0);

    // bisectRight: find insertion point for target in ends[0..hi-1]
    function bisectRight(arr: number[], target: number, lo: number, hi: number): number {
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (arr[mid] <= target) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    for (let i = 1; i <= n; i++) {
        const [end, start, prof] = jobs[i - 1];

        // Option 1: skip this job
        const skip = dp[i - 1];

        // Option 2: take this job
        // Find the latest job that ends <= this job's start time
        const j = bisectRight(ends, start, 0, i - 1);
        const take = prof + dp[j];

        dp[i] = Math.max(skip, take);
    }

    return dp[n];
}

C++

int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
    int n = startTime.size();

    // Combine and sort by end time
    vector<tuple<int, int, int>> jobs;
    for (int i = 0; i < n; i++) {
        jobs.emplace_back(endTime[i], startTime[i], profit[i]);
    }
    sort(jobs.begin(), jobs.end());

    // Extract sorted end times for binary search
    vector<int> ends;
    for (auto& [e, s, p] : jobs) ends.push_back(e);

    // dp[i] = max profit considering first i jobs (1-indexed)
    vector<int> dp(n + 1, 0);

    for (int i = 1; i <= n; i++) {
        auto [end, start, prof] = jobs[i - 1];

        // Option 1: skip this job
        int skip = dp[i - 1];

        // Option 2: take this job
        // Find the latest job that ends <= this job's start time
        // upper_bound finds first element > start; subtract begin to get index
        int j = (int)(upper_bound(ends.begin(), ends.begin() + i - 1, start) - ends.begin());
        int take = prof + dp[j];

        dp[i] = max(skip, take);
    }

    return dp[n];
}

Alternative — Top-down with memoization:

TypeScript

function jobSchedulingTopdown(
    startTime: number[], endTime: number[], profit: number[]
): number {
    const jobs: [number, number, number][] = [];
    for (let i = 0; i < startTime.length; i++) {
        jobs.push([startTime[i], endTime[i], profit[i]]);
    }
    jobs.sort((a, b) => a[0] - b[0]);

    const starts = jobs.map(j => j[0]);
    const n = jobs.length;

    function bisectLeft(arr: number[], target: number): number {
        let lo = 0, hi = arr.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (arr[mid] < target) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    const memo = new Map<number, number>();

    function dp(i: number): number {
        if (i >= n) return 0;
        if (memo.has(i)) return memo.get(i)!;

        // Skip job i
        const skip = dp(i + 1);
        // Take job i — find next job starting at or after this job's end
        const nextIdx = bisectLeft(starts, jobs[i][1]);
        const take = jobs[i][2] + dp(nextIdx);

        const result = Math.max(skip, take);
        memo.set(i, result);
        return result;
    }

    return dp(0);
}

C++

int jobSchedulingTopdown(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
    int n = startTime.size();

    vector<tuple<int, int, int>> jobs;
    for (int i = 0; i < n; i++) {
        jobs.emplace_back(startTime[i], endTime[i], profit[i]);
    }
    sort(jobs.begin(), jobs.end());

    vector<int> starts;
    for (auto& [s, e, p] : jobs) starts.push_back(s);

    vector<int> memo(n, -1);

    function<int(int)> dp = [&](int i) -> int {
        if (i >= n) return 0;
        if (memo[i] != -1) return memo[i];

        // Skip job i
        int skip = dp(i + 1);
        // Take job i — find next job starting at or after this job's end
        int nextIdx = (int)(lower_bound(starts.begin(), starts.end(), get<1>(jobs[i])) - starts.begin());
        int take = get<2>(jobs[i]) + dp(nextIdx);

        return memo[i] = max(skip, take);
    };

    return dp(0);
}

Watch out:

1. Binary search boundary errors. When searching for the last job ending <= start, use bisect_right(ends, start) on the subarray ends[0..i-2] (jobs before the current one). Using the full array would consider future jobs.
2. Sorting by start time vs end time. The bottom-up approach sorts by end time; the top-down approach sorts by start time. Mixing these up produces wrong results.
3. Off-by-one between 0-indexed jobs and 1-indexed DP. The DP array has n+1 entries. dp[0] is the base case (no jobs). dp[i] corresponds to jobs[i-1].

---

Complexity Analysis

	Time	Space
Brute Force (All subsets)	O(2^n)	O(n)
Optimal (DP + Binary Search)	O(n log n)	O(n)

Bottleneck: Sorting is O(n log n). The DP loop runs n times, each with an O(log n) binary search, giving O(n log n). Total: O(n log n). Space is O(n) for the DP array and the sorted jobs.

---

Edge Cases

1. All jobs overlap with each other — Pick the single most profitable job. DP correctly handles this: skip always beats take + 0 for less profitable jobs.
2. No overlaps at all — Take every job. Sum of all profits.
3. Single job — Return its profit.
4. Jobs with the same end time — Sorting is stable, and the binary search correctly handles ties (a job ending at time t is compatible with a job starting at time t).
5. Very large time values (10^9) — Binary search on actual end times, not on a time axis. No issue with coordinate range.
6. All jobs have the same profit — The answer is the maximum number of non-overlapping jobs. This reduces to the classic interval scheduling problem.

---

Related Problems

• LC 435 — Non-overlapping Intervals — Unweighted version: maximize the count of non-overlapping intervals. Greedy suffices.
• LC 1751 — Maximum Number of Events That Can Be Attended II — Same pattern but with a constraint on how many events you can attend (adds a dimension to DP).
• LC 646 — Maximum Length of Pair Chain — Greedy interval scheduling without weights.
• LC 1326 — Minimum Number of Taps to Open — Interval covering problem, related DP on intervals.

---

What is Expected at Each Level

Junior: Recognize the overlap constraint. Write the recursive solution. May not see the binary search optimization — instead do linear scan for the last non-overlapping job.

Mid-level: Sort by end time. Write the DP + Binary Search solution. Correctly use bisect_right. Discuss time complexity and why binary search is necessary (linear scan would make it O(n^2)).

Senior: Write the solution quickly and discuss both bottom-up and top-down variants. Explain why sorting by end time is natural for bottom-up and sorting by start time works for top-down. Discuss extensions: what if you can do at most k jobs? (Add a dimension to DP.) What about online/streaming jobs? Connect to real-world scheduling systems.