Maximum Profit in Job Scheduling

🎯

Maximum Profit in Job Scheduling

hardDPAmazonGoogleFacebook

Imagine you are a freelancer with multiple job offers, each with a start time, end time, and profit. You want to schedule jobs to maximize your total earnings without overlapping any jobs.

💡 This problem is a classic example of weighted interval scheduling, where the challenge is to select non-overlapping intervals to maximize profit. Beginners often struggle because greedy approaches fail and the problem requires combining sorting, binary search, and dynamic programming.

📋

Problem Statement

Given n jobs where every job is represented as (startTime, endTime, profit), find the maximum profit you can earn by scheduling non-overlapping jobs. You may choose to skip some jobs. Return the maximum profit achievable.

1 ≤ n ≤ 10^51 ≤ startTime[i], endTime[i], profit[i] ≤ 10^9startTime[i] < endTime[i]

💡

Example

Input"startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]"

Output150

Schedule jobs 1 (1-3, profit 20), 4 (4-6, profit 70), and 5 (6-9, profit 60) for total 150.

• All jobs overlap completely → output is max single job profit
• Jobs with same start and end times but different profits → pick highest profit job
• Jobs sorted in descending order of end time → algorithm must still work
• Jobs with large gaps between intervals → algorithm should handle efficiently

🔁

Why DP?

Why greedy fails:

A greedy approach that always picks the job with the earliest end time or highest profit fails because it may exclude a combination of jobs that yield higher total profit. For example, picking the earliest finishing job might block a later job with much higher profit.

DP state:

dp[i] represents the maximum profit achievable by scheduling jobs from the first i jobs (sorted by end time).

Recurrence:dp[i] = max(dp[i-1], profit[i] + dp[lastNonConflictingJob(i)])

For each job i, either skip it (dp[i-1]) or take it and add its profit to the best compatible job's profit.

⚠️

Common Mistakes

Not sorting jobs by end time

Binary search and DP logic fail, producing incorrect results

✅ Always sort jobs by end time before DP

Using start time instead of end time for sorting

DP dependencies break, leading to wrong answers

✅ Sort by end time to ensure compatibility checks work

Incorrect binary search bounds

Finds wrong compatible job index, causing suboptimal profit

✅ Use bisect_right or equivalent to find last job ending before current job starts

Not caching results in recursion

Exponential time complexity and TLE

✅ Use memoization or tabulation to store intermediate results

Off-by-one errors in indexing dp or binary search

Runtime errors or incorrect results

✅ Carefully handle indices and test edge cases

🧠

Brute Force (Pure Recursion)

💡 Starting with brute force helps understand the problem's exponential nature and why optimization is necessary.

Intuition

Try every job and recursively decide whether to include it or not, ensuring no overlapping jobs are chosen.

Algorithm

1. Sort jobs by start time or end time.
2. For each job, recursively decide to include it if it doesn't overlap with previously chosen jobs or skip it.
3. Return the maximum profit from all recursive choices.
4. Use a helper function to check for overlaps.

💡 The recursion tree grows exponentially because each job leads to two choices, making it hard to track without memoization.

Recurrence:f(i) = max(f(i-1), profit[i] + f(j)) where j < i and jobs[j].endTime <= jobs[i].startTime

</>

Code

from typing import List

def jobScheduling(startTime: List[int], endTime: List[int], profit: List[int]) -> int:
    jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[0])
    n = len(jobs)

    def can_take(curr, prev):
        return jobs[prev][1] <= jobs[curr][0]

    def dfs(i, prev):
        if i == n:
            return 0
        # skip current job
        skip = dfs(i + 1, prev)
        # take current job if no overlap
        take = 0
        if prev == -1 or can_take(i, prev):
            take = jobs[i][2] + dfs(i + 1, i)
        return max(skip, take)

    return dfs(0, -1)

# Driver code
if __name__ == '__main__':
    print(jobScheduling([1,2,3,4,6], [3,5,10,6,9], [20,20,100,70,60]))  # Expected 150

Line Notes

jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[0])Sort jobs by start time to process in order

def can_take(curr, prev):Helper to check if current job can be taken after previous job

if i == n:Base case: no more jobs to process

skip = dfs(i + 1, prev)Option 1: skip current job and move forward

import java.util.*;

public class Solution {
    static class Job {
        int start, end, profit;
        Job(int s, int e, int p) { start = s; end = e; profit = p; }
    }

    public static int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        Job[] jobs = new Job[n];
        for (int i = 0; i < n; i++) {
            jobs[i] = new Job(startTime[i], endTime[i], profit[i]);
        }
        Arrays.sort(jobs, Comparator.comparingInt(j -> j.start));

        return dfs(jobs, 0, -1);
    }

    private static int dfs(Job[] jobs, int i, int prev) {
        if (i == jobs.length) return 0;
        int skip = dfs(jobs, i + 1, prev);
        int take = 0;
        if (prev == -1 || jobs[prev].end <= jobs[i].start) {
            take = jobs[i].profit + dfs(jobs, i + 1, i);
        }
        return Math.max(skip, take);
    }

    public static void main(String[] args) {
        int[] startTime = {1,2,3,4,6};
        int[] endTime = {3,5,10,6,9};
        int[] profit = {20,20,100,70,60};
        System.out.println(jobScheduling(startTime, endTime, profit)); // Expected 150
    }
}

Line Notes

Job[] jobs = new Job[n];Create array of jobs for easier sorting and access

Arrays.sort(jobs, Comparator.comparingInt(j -> j.start));Sort jobs by start time to process in order

if (i == jobs.length) return 0;Base case: no more jobs to consider

int skip = dfs(jobs, i + 1, prev);Option to skip current job

#include <bits/stdc++.h>
using namespace std;

struct Job {
    int start, end, profit;
    Job(int s, int e, int p) : start(s), end(e), profit(p) {}
};

int dfs(const vector<Job>& jobs, int i, int prev) {
    if (i == (int)jobs.size()) return 0;
    int skip = dfs(jobs, i + 1, prev);
    int take = 0;
    if (prev == -1 || jobs[prev].end <= jobs[i].start) {
        take = jobs[i].profit + dfs(jobs, i + 1, i);
    }
    return max(skip, take);
}

int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
    int n = (int)startTime.size();
    vector<Job> jobs;
    for (int i = 0; i < n; i++) {
        jobs.emplace_back(startTime[i], endTime[i], profit[i]);
    }
    sort(jobs.begin(), jobs.end(), [](const Job& a, const Job& b) {
        return a.start < b.start;
    });
    return dfs(jobs, 0, -1);
}

int main() {
    vector<int> startTime = {1,2,3,4,6};
    vector<int> endTime = {3,5,10,6,9};
    vector<int> profit = {20,20,100,70,60};
    cout << jobScheduling(startTime, endTime, profit) << '\n'; // Expected 150
    return 0;
}

Line Notes

vector<Job> jobs;Store jobs in a struct vector for sorting and access

sort(jobs.begin(), jobs.end(), ...Sort jobs by start time to process sequentially

if (i == (int)jobs.size()) return 0;Base case: no jobs left to consider

int skip = dfs(jobs, i + 1, prev);Option to skip current job and recurse

function jobScheduling(startTime, endTime, profit) {
    const jobs = startTime.map((s, i) => [s, endTime[i], profit[i]]);
    jobs.sort((a, b) => a[0] - b[0]);
    const n = jobs.length;

    function canTake(curr, prev) {
        return prev === -1 || jobs[prev][1] <= jobs[curr][0];
    }

    function dfs(i, prev) {
        if (i === n) return 0;
        const skip = dfs(i + 1, prev);
        let take = 0;
        if (canTake(i, prev)) {
            take = jobs[i][2] + dfs(i + 1, i);
        }
        return Math.max(skip, take);
    }

    return dfs(0, -1);
}

// Test
console.log(jobScheduling([1,2,3,4,6], [3,5,10,6,9], [20,20,100,70,60])); // Expected 150

Line Notes

const jobs = startTime.map((s, i) => [s, endTime[i], profit[i]]);Combine job info into one array for sorting

jobs.sort((a, b) => a[0] - b[0]);Sort jobs by start time to process in order

if (i === n) return 0;Base case: no more jobs to consider

const skip = dfs(i + 1, prev);Option to skip current job and recurse

⏱

Complexity

TimeO(2^n)

SpaceO(n) recursion stack

Each job leads to two recursive calls, resulting in exponential time.

💡 For n=20, this means over a million calls, which is impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem's structure.

🧠

Memoization with Sorting and Binary Search

💡 Memoization avoids recomputing states by caching results, making the solution efficient enough for large inputs.

Intuition

Sort jobs by end time, then for each job, use binary search to find the last non-overlapping job and recursively compute max profit with memoization.

Algorithm

1. Sort jobs by end time.
2. For each job, use binary search to find the last job that doesn't overlap.
3. Use recursion with memoization to compute max profit including or excluding current job.
4. Return the maximum profit from all jobs.

💡 Memoization prunes the recursion tree drastically, and binary search efficiently finds compatible jobs.

Recurrence:dp[i] = max(dp[i-1], profit[i] + dp[lastNonConflictingJob(i)])

</>

Code

from typing import List
import bisect

def jobScheduling(startTime: List[int], endTime: List[int], profit: List[int]) -> int:
    jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])
    n = len(jobs)
    ends = [job[1] for job in jobs]
    memo = {}

    def dfs(i):
        if i < 0:
            return 0
        if i in memo:
            return memo[i]
        # Find last job that ends before jobs[i] starts
        start_i = jobs[i][0]
        idx = bisect.bisect_right(ends, start_i - 1) - 1
        take = jobs[i][2] + dfs(idx)
        skip = dfs(i - 1)
        memo[i] = max(take, skip)
        return memo[i]

    return dfs(n - 1)

# Driver code
if __name__ == '__main__':
    print(jobScheduling([1,2,3,4,6], [3,5,10,6,9], [20,20,100,70,60]))  # Expected 150

Line Notes

jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])Sort jobs by end time for DP order

ends = [job[1] for job in jobs]Extract end times for binary search

idx = bisect.bisect_right(ends, start_i - 1) - 1Find last non-overlapping job index using binary search

memo[i] = max(take, skip)Cache result to avoid recomputation

import java.util.*;

public class Solution {
    static class Job {
        int start, end, profit;
        Job(int s, int e, int p) { start = s; end = e; profit = p; }
    }

    public static int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        Job[] jobs = new Job[n];
        for (int i = 0; i < n; i++) {
            jobs[i] = new Job(startTime[i], endTime[i], profit[i]);
        }
        Arrays.sort(jobs, Comparator.comparingInt(j -> j.end));

        int[] ends = new int[n];
        for (int i = 0; i < n; i++) ends[i] = jobs[i].end;

        Map<Integer, Integer> memo = new HashMap<>();

        return dfs(jobs, ends, n - 1, memo);
    }

    private static int dfs(Job[] jobs, int[] ends, int i, Map<Integer, Integer> memo) {
        if (i < 0) return 0;
        if (memo.containsKey(i)) return memo.get(i);
        int start_i = jobs[i].start;
        int idx = binarySearch(ends, start_i - 1);
        int take = jobs[i].profit + dfs(jobs, ends, idx, memo);
        int skip = dfs(jobs, ends, i - 1, memo);
        int res = Math.max(take, skip);
        memo.put(i, res);
        return res;
    }

    private static int binarySearch(int[] ends, int target) {
        int low = 0, high = ends.length - 1, res = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (ends[mid] <= target) {
                res = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] startTime = {1,2,3,4,6};
        int[] endTime = {3,5,10,6,9};
        int[] profit = {20,20,100,70,60};
        System.out.println(jobScheduling(startTime, endTime, profit)); // Expected 150
    }
}

Line Notes

Arrays.sort(jobs, Comparator.comparingInt(j -> j.end));Sort jobs by end time for DP order

int[] ends = new int[n];Store end times for binary search

int idx = binarySearch(ends, start_i - 1);Find last non-overlapping job index

memo.put(i, res);Cache computed result to avoid recomputation

#include <bits/stdc++.h>
using namespace std;

struct Job {
    int start, end, profit;
    Job(int s, int e, int p) : start(s), end(e), profit(p) {}
};

int binarySearch(const vector<int>& ends, int target) {
    int low = 0, high = (int)ends.size() - 1, res = -1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (ends[mid] <= target) {
            res = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return res;
}

int dfs(const vector<Job>& jobs, const vector<int>& ends, int i, unordered_map<int,int>& memo) {
    if (i < 0) return 0;
    if (memo.count(i)) return memo[i];
    int start_i = jobs[i].start;
    int idx = binarySearch(ends, start_i - 1);
    int take = jobs[i].profit + dfs(jobs, ends, idx, memo);
    int skip = dfs(jobs, ends, i - 1, memo);
    return memo[i] = max(take, skip);
}

int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
    int n = (int)startTime.size();
    vector<Job> jobs;
    for (int i = 0; i < n; i++) {
        jobs.emplace_back(startTime[i], endTime[i], profit[i]);
    }
    sort(jobs.begin(), jobs.end(), [](const Job& a, const Job& b) {
        return a.end < b.end;
    });
    vector<int> ends(n);
    for (int i = 0; i < n; i++) ends[i] = jobs[i].end;
    unordered_map<int,int> memo;
    return dfs(jobs, ends, n - 1, memo);
}

int main() {
    vector<int> startTime = {1,2,3,4,6};
    vector<int> endTime = {3,5,10,6,9};
    vector<int> profit = {20,20,100,70,60};
    cout << jobScheduling(startTime, endTime, profit) << '\n'; // Expected 150
    return 0;
}

Line Notes

sort(jobs.begin(), jobs.end(), ...Sort jobs by end time for DP order

int idx = binarySearch(ends, start_i - 1);Find last compatible job index using binary search

if (memo.count(i)) return memo[i];Return cached result if available

return memo[i] = max(take, skip);Store and return max profit for job i

function jobScheduling(startTime, endTime, profit) {
    const jobs = startTime.map((s, i) => [s, endTime[i], profit[i]]);
    jobs.sort((a, b) => a[1] - b[1]);
    const ends = jobs.map(j => j[1]);
    const n = jobs.length;
    const memo = new Map();

    function binarySearch(target) {
        let low = 0, high = n - 1, res = -1;
        while (low <= high) {
            const mid = Math.floor((low + high) / 2);
            if (ends[mid] <= target) {
                res = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return res;
    }

    function dfs(i) {
        if (i < 0) return 0;
        if (memo.has(i)) return memo.get(i);
        const start_i = jobs[i][0];
        const idx = binarySearch(start_i - 1);
        const take = jobs[i][2] + dfs(idx);
        const skip = dfs(i - 1);
        const res = Math.max(take, skip);
        memo.set(i, res);
        return res;
    }

    return dfs(n - 1);
}

// Test
console.log(jobScheduling([1,2,3,4,6], [3,5,10,6,9], [20,20,100,70,60])); // Expected 150

Line Notes

jobs.sort((a, b) => a[1] - b[1]);Sort jobs by end time for DP order

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

const idx = binarySearch(start_i - 1);Find last non-overlapping job index

memo.set(i, res);Cache computed result to avoid recomputation

⏱

Complexity

TimeO(n log n)

SpaceO(n)

Sorting takes O(n log n), binary search O(log n) per job, and memoization ensures each state is computed once.

💡 For n=10^5, this approach is efficient and practical.

Interview Verdict: Accepted

This approach is optimal for large inputs and commonly expected in interviews.

🧠

Tabulation (Bottom-Up DP with Binary Search)

💡 Tabulation builds the solution iteratively, which is often easier to debug and understand than recursion with memoization.

Intuition

Sort jobs by end time, then iteratively compute dp[i] as the max profit including or excluding job i, using binary search to find compatible jobs.

Algorithm

1. Sort jobs by end time.
2. Initialize dp array where dp[i] stores max profit up to job i.
3. For each job i, use binary search to find last non-overlapping job j.
4. Set dp[i] = max(dp[i-1], profit[i] + dp[j]) and continue.
5. Return dp[n-1] as the answer.

💡 Tabulation avoids recursion overhead and makes dependencies explicit.

Recurrence:dp[i] = max(dp[i-1], profit[i] + dp[lastNonConflictingJob(i)])

</>

Code

from typing import List
import bisect

def jobScheduling(startTime: List[int], endTime: List[int], profit: List[int]) -> int:
    jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])
    n = len(jobs)
    ends = [job[1] for job in jobs]
    dp = [0] * n

    for i in range(n):
        start_i, end_i, profit_i = jobs[i]
        idx = bisect.bisect_right(ends, start_i - 1) - 1
        take = profit_i + (dp[idx] if idx >= 0 else 0)
        skip = dp[i - 1] if i > 0 else 0
        dp[i] = max(take, skip)

    return dp[-1]

# Driver code
if __name__ == '__main__':
    print(jobScheduling([1,2,3,4,6], [3,5,10,6,9], [20,20,100,70,60]))  # Expected 150

Line Notes

jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])Sort jobs by end time for DP order

dp = [0] * nInitialize dp array to store max profit up to each job

idx = bisect.bisect_right(ends, start_i - 1) - 1Find last compatible job index using binary search

dp[i] = max(take, skip)Choose max profit between taking or skipping current job

import java.util.*;

public class Solution {
    static class Job {
        int start, end, profit;
        Job(int s, int e, int p) { start = s; end = e; profit = p; }
    }

    public static int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        Job[] jobs = new Job[n];
        for (int i = 0; i < n; i++) {
            jobs[i] = new Job(startTime[i], endTime[i], profit[i]);
        }
        Arrays.sort(jobs, Comparator.comparingInt(j -> j.end));

        int[] ends = new int[n];
        for (int i = 0; i < n; i++) ends[i] = jobs[i].end;

        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            int take = jobs[i].profit;
            int idx = binarySearch(ends, jobs[i].start - 1);
            if (idx != -1) take += dp[idx];
            int skip = i > 0 ? dp[i - 1] : 0;
            dp[i] = Math.max(take, skip);
        }
        return dp[n - 1];
    }

    private static int binarySearch(int[] ends, int target) {
        int low = 0, high = ends.length - 1, res = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (ends[mid] <= target) {
                res = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] startTime = {1,2,3,4,6};
        int[] endTime = {3,5,10,6,9};
        int[] profit = {20,20,100,70,60};
        System.out.println(jobScheduling(startTime, endTime, profit)); // Expected 150
    }
}

Line Notes

int[] dp = new int[n];DP array stores max profit up to each job

int idx = binarySearch(ends, jobs[i].start - 1);Find last compatible job index

dp[i] = Math.max(take, skip);Choose max profit between taking or skipping job i

return dp[n - 1];Final answer is max profit considering all jobs

#include <bits/stdc++.h>
using namespace std;

struct Job {
    int start, end, profit;
    Job(int s, int e, int p) : start(s), end(e), profit(p) {}
};

int binarySearch(const vector<int>& ends, int target) {
    int low = 0, high = (int)ends.size() - 1, res = -1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (ends[mid] <= target) {
            res = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return res;
}

int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
    int n = (int)startTime.size();
    vector<Job> jobs;
    for (int i = 0; i < n; i++) {
        jobs.emplace_back(startTime[i], endTime[i], profit[i]);
    }
    sort(jobs.begin(), jobs.end(), [](const Job& a, const Job& b) {
        return a.end < b.end;
    });
    vector<int> ends(n);
    for (int i = 0; i < n; i++) ends[i] = jobs[i].end;
    vector<int> dp(n, 0);
    for (int i = 0; i < n; i++) {
        int take = jobs[i].profit;
        int idx = binarySearch(ends, jobs[i].start - 1);
        if (idx != -1) take += dp[idx];
        int skip = i > 0 ? dp[i - 1] : 0;
        dp[i] = max(take, skip);
    }
    return dp[n - 1];
}

int main() {
    vector<int> startTime = {1,2,3,4,6};
    vector<int> endTime = {3,5,10,6,9};
    vector<int> profit = {20,20,100,70,60};
    cout << jobScheduling(startTime, endTime, profit) << '\n'; // Expected 150
    return 0;
}

Line Notes

vector<int> dp(n, 0);DP array to store max profit up to each job

int idx = binarySearch(ends, jobs[i].start - 1);Find last compatible job index

dp[i] = max(take, skip);Choose max profit between taking or skipping job i

return dp[n - 1];Return max profit after considering all jobs

function jobScheduling(startTime, endTime, profit) {
    const jobs = startTime.map((s, i) => [s, endTime[i], profit[i]]);
    jobs.sort((a, b) => a[1] - b[1]);
    const ends = jobs.map(j => j[1]);
    const n = jobs.length;
    const dp = new Array(n).fill(0);

    function binarySearch(target) {
        let low = 0, high = n - 1, res = -1;
        while (low <= high) {
            const mid = Math.floor((low + high) / 2);
            if (ends[mid] <= target) {
                res = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return res;
    }

    for (let i = 0; i < n; i++) {
        const [start_i, , profit_i] = jobs[i];
        const idx = binarySearch(start_i - 1);
        const take = profit_i + (idx >= 0 ? dp[idx] : 0);
        const skip = i > 0 ? dp[i - 1] : 0;
        dp[i] = Math.max(take, skip);
    }

    return dp[n - 1];
}

// Test
console.log(jobScheduling([1,2,3,4,6], [3,5,10,6,9], [20,20,100,70,60])); // Expected 150

Line Notes

const dp = new Array(n).fill(0);Initialize dp array for max profit up to each job

const idx = binarySearch(start_i - 1);Find last compatible job index

dp[i] = Math.max(take, skip);Choose max profit between taking or skipping job i

return dp[n - 1];Return max profit after processing all jobs

⏱

Complexity

TimeO(n log n)

SpaceO(n)

Sorting and binary search dominate time complexity; dp array uses linear space.

💡 This approach is efficient and preferred in interviews for clarity and performance.

Interview Verdict: Accepted

Tabulation is often preferred for its iterative clarity and ease of debugging.

🧠

Space Optimized DP (Using 1D DP Array)

💡 This approach uses the same tabulation logic but emphasizes minimal extra space usage, suitable when memory is constrained.

Intuition

Since dp[i] depends only on dp values with smaller indices, a single 1D dp array suffices without additional structures.

Algorithm

1. Sort jobs by end time.
2. Initialize a 1D dp array to store max profit up to each job.
3. For each job, use binary search to find the last compatible job.
4. Update dp[i] with max of skipping or taking the job plus dp of compatible job.
5. Return dp[n-1] as the maximum profit.

💡 This approach is essentially the same as tabulation but highlights minimal memory usage.

Recurrence:dp[i] = max(dp[i-1], profit[i] + dp[lastNonConflictingJob(i)])

</>

Code

from typing import List
import bisect

def jobScheduling(startTime: List[int], endTime: List[int], profit: List[int]) -> int:
    jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])
    n = len(jobs)
    ends = [job[1] for job in jobs]
    dp = [0] * n

    for i in range(n):
        start_i, end_i, profit_i = jobs[i]
        idx = bisect.bisect_right(ends, start_i - 1) - 1
        take = profit_i + (dp[idx] if idx >= 0 else 0)
        skip = dp[i - 1] if i > 0 else 0
        dp[i] = max(take, skip)

    return dp[-1]

# Driver code
if __name__ == '__main__':
    print(jobScheduling([1,2,3,4,6], [3,5,10,6,9], [20,20,100,70,60]))  # Expected 150

Line Notes

dp = [0] * nInitialize 1D dp array to store max profit up to each job

idx = bisect.bisect_right(ends, start_i - 1) - 1Find last compatible job index using binary search

dp[i] = max(take, skip)Update dp with max profit including or excluding current job

return dp[-1]Return maximum profit after processing all jobs

import java.util.*;

public class Solution {
    static class Job {
        int start, end, profit;
        Job(int s, int e, int p) { start = s; end = e; profit = p; }
    }

    public static int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        Job[] jobs = new Job[n];
        for (int i = 0; i < n; i++) {
            jobs[i] = new Job(startTime[i], endTime[i], profit[i]);
        }
        Arrays.sort(jobs, Comparator.comparingInt(j -> j.end));

        int[] ends = new int[n];
        for (int i = 0; i < n; i++) ends[i] = jobs[i].end;

        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            int take = jobs[i].profit;
            int idx = binarySearch(ends, jobs[i].start - 1);
            if (idx != -1) take += dp[idx];
            int skip = i > 0 ? dp[i - 1] : 0;
            dp[i] = Math.max(take, skip);
        }
        return dp[n - 1];
    }

    private static int binarySearch(int[] ends, int target) {
        int low = 0, high = ends.length - 1, res = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (ends[mid] <= target) {
                res = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] startTime = {1,2,3,4,6};
        int[] endTime = {3,5,10,6,9};
        int[] profit = {20,20,100,70,60};
        System.out.println(jobScheduling(startTime, endTime, profit)); // Expected 150
    }
}

Line Notes

int[] dp = new int[n];1D dp array stores max profit up to each job

int idx = binarySearch(ends, jobs[i].start - 1);Find last compatible job index

dp[i] = Math.max(take, skip);Update dp with max profit including or excluding job i

return dp[n - 1];Return max profit after all jobs

#include <bits/stdc++.h>
using namespace std;

struct Job {
    int start, end, profit;
    Job(int s, int e, int p) : start(s), end(e), profit(p) {}
};

int binarySearch(const vector<int>& ends, int target) {
    int low = 0, high = (int)ends.size() - 1, res = -1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (ends[mid] <= target) {
            res = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return res;
}

int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
    int n = (int)startTime.size();
    vector<Job> jobs;
    for (int i = 0; i < n; i++) {
        jobs.emplace_back(startTime[i], endTime[i], profit[i]);
    }
    sort(jobs.begin(), jobs.end(), [](const Job& a, const Job& b) {
        return a.end < b.end;
    });
    vector<int> ends(n);
    for (int i = 0; i < n; i++) ends[i] = jobs[i].end;
    vector<int> dp(n, 0);
    for (int i = 0; i < n; i++) {
        int take = jobs[i].profit;
        int idx = binarySearch(ends, jobs[i].start - 1);
        if (idx != -1) take += dp[idx];
        int skip = i > 0 ? dp[i - 1] : 0;
        dp[i] = max(take, skip);
    }
    return dp[n - 1];
}

int main() {
    vector<int> startTime = {1,2,3,4,6};
    vector<int> endTime = {3,5,10,6,9};
    vector<int> profit = {20,20,100,70,60};
    cout << jobScheduling(startTime, endTime, profit) << '\n'; // Expected 150
    return 0;
}

Line Notes

vector<int> dp(n, 0);1D dp array for max profit up to each job

int idx = binarySearch(ends, jobs[i].start - 1);Find last compatible job index

dp[i] = max(take, skip);Update dp with max profit including or excluding job i

return dp[n - 1];Return max profit after processing all jobs

function jobScheduling(startTime, endTime, profit) {
    const jobs = startTime.map((s, i) => [s, endTime[i], profit[i]]);
    jobs.sort((a, b) => a[1] - b[1]);
    const ends = jobs.map(j => j[1]);
    const n = jobs.length;
    const dp = new Array(n).fill(0);

    function binarySearch(target) {
        let low = 0, high = n - 1, res = -1;
        while (low <= high) {
            const mid = Math.floor((low + high) / 2);
            if (ends[mid] <= target) {
                res = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return res;
    }

    for (let i = 0; i < n; i++) {
        const [start_i, , profit_i] = jobs[i];
        const idx = binarySearch(start_i - 1);
        const take = profit_i + (idx >= 0 ? dp[idx] : 0);
        const skip = i > 0 ? dp[i - 1] : 0;
        dp[i] = Math.max(take, skip);
    }

    return dp[n - 1];
}

// Test
console.log(jobScheduling([1,2,3,4,6], [3,5,10,6,9], [20,20,100,70,60])); // Expected 150

Line Notes

const dp = new Array(n).fill(0);Initialize 1D dp array for max profit

const idx = binarySearch(start_i - 1);Find last compatible job index

dp[i] = Math.max(take, skip);Update dp with max profit including or excluding job i

return dp[n - 1];Return max profit after processing all jobs

⏱

Complexity

TimeO(n log n)

SpaceO(n)

Same as tabulation but emphasizes minimal extra space usage.

💡 This is the most memory-efficient DP approach for this problem.

Interview Verdict: Accepted

Space optimization is a nice-to-have but not always required in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 Memoization or tabulation with binary search is the best approach to code in interviews for clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes (deep recursion)	Yes	Mention only - never code
2. Memoization with Binary Search	O(n log n)	O(n)	No (due to memoization pruning)	Yes	Preferred approach to code
3. Tabulation (Bottom-Up DP)	O(n log n)	O(n)	No	Yes	Good alternative to memoization
4. Space Optimized DP	O(n log n)	O(n)	No	Yes	Mention if asked about space optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify problem constraints and input format.Explain brute force recursion to show problem structure.Introduce memoization with binary search to optimize.Present tabulation as an iterative alternative.Mention space optimization if asked.Code the memoization or tabulation approach.Test with sample and edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Understanding of interval scheduling, ability to optimize recursion with DP and binary search, and clarity in explaining tradeoffs.

Common Follow-ups

• What if jobs can overlap partially but you can work on multiple simultaneously? → Use different approach.
• How to reconstruct the job schedule for max profit? → Store choices and backtrack.
• Can we solve without sorting? → Sorting is essential here.
• What if profits are negative? → DP still works but consider skipping negative profit jobs.

💡 These follow-ups test deeper understanding and ability to adapt the solution.

🔍

Pattern Recognition

When to Use

1) Problem involves scheduling intervals with profits; 2) Need to maximize total profit; 3) Jobs cannot overlap; 4) Input size requires efficient solution.

Signature Phrases

'maximum profit you can earn by scheduling jobs''no two jobs overlap''startTime, endTime, profit'

NOT This Pattern When

Unweighted interval scheduling solved by greedy; knapsack problems without intervals.

Similar Problems

Weighted Interval Scheduling - classic DP problem with intervalsJob Scheduling with Deadlines - greedy variant with deadlinesActivity Selection Problem - unweighted interval scheduling

Practice

1. You are given a set of items, each with a weight and a value, and a knapsack with a maximum weight capacity. You want to maximize the total value of items placed in the knapsack without exceeding its capacity. Which algorithmic approach guarantees finding the optimal solution for this problem?

easy

A. A greedy algorithm that picks items with the highest value-to-weight ratio first.

B. Dynamic programming that considers including or excluding each item for every capacity up to the maximum.

C. A simple recursive approach without memoization that tries all subsets of items.

D. A breadth-first search exploring all possible combinations of items.

Solution

1. Step 1: Understand problem constraints and overlapping subproblems

   The problem requires maximizing value without exceeding capacity, which is a classic optimization problem with overlapping subproblems suitable for dynamic programming.

2. Step 2: Identify algorithmic approach that guarantees optimality

   Greedy algorithms fail because picking locally optimal items (highest value/weight) does not guarantee global optimum. Exhaustive search is correct but inefficient. Dynamic programming systematically explores all item inclusion/exclusion states with memoization, ensuring optimality.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP solves 0/1 Knapsack optimally by exploring all states [OK]

Hint: DP with inclusion/exclusion ensures optimal solution [OK]

Common Mistakes:

• Greedy approach works for fractional knapsack, not 0/1 knapsack.

2. Given the following code for lastStoneWeightII, what is the returned value when stones = [1, 2, 3]?

easy

A. 1

B. 0

C. 2

D. 3

Solution

1. Step 1: Calculate total and half

   Total = 6, half = 3. dp array size = 4, dp[0] = true initially.

2. Step 2: Update dp for each stone

   For weight=1: dp[1]=true; for weight=2: dp[3]=true (since dp[1] was true), dp[2]=true; for weight=3: dp[3]=true remains.

3. Step 3: Find largest w ≤ half with dp[w] = true

   dp[3] is true, so minimal difference = total - 2*3 = 6 - 6 = 0.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Subset {1,2,3} sums to 6; partition into {3} and {1,2} sums 3 and 3 -> difference 0 [OK]

Hint: Check dp array for sums up to half total [OK]

Common Mistakes:

• Returning total instead of minimal difference
• Off-by-one error in dp indexing
• Not iterating backwards in dp update

3. Consider the following Python function implementing the DP with bitmask tabulation approach for partitioning an array into k equal sum subsets. What is the return value when called with nums = [1, 2, 3, 4] and k = 2?

from typing import List

def canPartitionKSubsets(nums: List[int], k: int) -> bool:
    total = sum(nums)
    if total % k != 0:
        return False
    target = total // k
    n = len(nums)
    nums.sort()
    if nums[-1] > target:
        return False

    dp = [-1] * (1 << n)
    dp[0] = 0

    for mask in range(1 << n):
        if dp[mask] == -1:
            continue
        for i in range(n):
            if (mask & (1 << i)) == 0 and dp[mask] + nums[i] <= target:
                next_mask = mask | (1 << i)
                if dp[next_mask] == -1:
                    dp[next_mask] = (dp[mask] + nums[i]) % target

    return dp[(1 << n) - 1] == 0

easy

A. True

B. False

C. Raises an exception due to index error

D. Returns None

Solution

1. Step 1: Calculate total and target

   Sum is 10, k=2, target subset sum = 5.

2. Step 2: Trace dp updates

   DP explores subsets; for example, {1,4} and {2,3} both sum to 5, so dp[(1<<4)-1] = 0, returning True.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Partition exists: [1,4] and [2,3] [OK]

Hint: Sum divisible by k and dp final state 0 means partition possible [OK]

Common Mistakes:

• Confusing dp array indexing or bitmask operations
• Forgetting to check if largest element exceeds target

4. What is the time complexity of the space-optimized bottom-up dynamic programming solution for the coin change minimum coins problem, given n coins and amount S?

medium

A. O(n * S) because for each amount up to S, all n coins are checked

B. O(n^S) due to exploring all combinations recursively

C. O(S^2) since the dp array is updated for each sub-amount multiple times

D. O(n + S) as the algorithm iterates once over coins and once over amounts

Solution

1. Step 1: Identify loops in the bottom-up DP

   Outer loop runs from 1 to S (amount), inner loop runs over n coins.

2. Step 2: Calculate total operations

   Each dp[i] is updated by checking all n coins, so total operations = n * S.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Nested loops over amount and coins -> O(n * S) [OK]

Hint: Nested loops over amount and coins yield O(n*S) [OK]

Common Mistakes:

• Confusing recursion exponential time with DP
• Assuming quadratic due to dp updates

5. The following code attempts to solve the subset sum problem using space-optimized DP. Identify the bug that causes incorrect results on some inputs.

medium

A. Line 2: dp[0] should be initialized to False

B. Line 6: dp[w] should be assigned dp[w - num] only, not ORed

C. Line 4: The outer loop should iterate backwards over nums

D. Line 5: The inner loop iterates forwards instead of backwards

Solution

1. Step 1: Understand dp update direction

   Iterating forwards causes dp[w] to use updated dp[w - num] from the same iteration, leading to overcounting.

2. Step 2: Correct iteration direction

   Iterating backwards ensures dp[w - num] is from previous iteration, preserving correctness.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Forward iteration breaks subset sum correctness -> bug at line 5 [OK]

Hint: DP must iterate sums backward to avoid reuse in same iteration [OK]

Common Mistakes:

• Initializing dp[0] incorrectly
• Misusing OR in dp update
• Wrong loop order over nums