Bird
Raised Fist0
Interview Prepdp-knapsackhardAmazonGoogleFacebook

Maximum Profit in Job Scheduling

Choose your preparation mode4 modes available
🎯
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.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute ForceO(2^n)O(n) recursion stackYes (deep recursion)YesMention only - never code
2. Memoization with Binary SearchO(n log n)O(n)No (due to memoization pruning)YesPreferred approach to code
3. Tabulation (Bottom-Up DP)O(n log n)O(n)NoYesGood alternative to memoization
4. Space Optimized DPO(n log n)O(n)NoYesMention 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/5)
1. You need to find the minimum number of coins required to make up a given amount from an unlimited supply of given coin denominations. Which algorithmic approach guarantees an optimal solution for this problem?
easy
A. Greedy algorithm that picks the largest coin first until the amount is reached
B. Dynamic programming using a 1D array to store minimum coins needed for all amounts up to the target
C. Pure brute force recursion trying all combinations without memoization
D. Sorting coins and using binary search to find the best coin for each sub-amount

Solution

  1. Step 1: Understand problem constraints

    The problem requires minimum coins for any amount with unlimited coin usage, which fits unbounded knapsack pattern.
  2. Step 2: Identify algorithm that guarantees optimality

    Greedy fails for some coin sets; brute force is correct but inefficient; DP with 1D array efficiently computes minimum coins for all sub-amounts ensuring optimality.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    DP solves overlapping subproblems optimally [OK]
Hint: Unbounded knapsack DP ensures optimal minimum coins [OK]
Common Mistakes:
  • Assuming greedy always works
  • Ignoring memoization for efficiency
2. You need to find the number of distinct ways to make a target amount using unlimited supply of given coin denominations. Which algorithmic approach guarantees counting all unique combinations without overcounting permutations?
easy
A. Greedy algorithm that picks the largest coin first until the amount is reached
B. Dynamic programming using a 1D array iterating coins first, then amounts
C. Backtracking exploring all permutations of coins to sum to the amount
D. Sorting coins and using two pointers to find pairs that sum to the amount

Solution

  1. Step 1: Understand problem constraints

    The problem requires counting unique combinations, not permutations, of coins to reach the target amount.
  2. Step 2: Identify algorithm that counts combinations without duplicates

    Dynamic programming iterating coins first ensures each coin is considered in order, avoiding counting permutations multiple times. The 1D DP approach efficiently accumulates counts for each amount.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    DP with coin-first iteration counts combinations correctly [OK]
Hint: Coin-first DP avoids permutation overcounting [OK]
Common Mistakes:
  • Using greedy misses some combinations
  • Counting permutations instead of combinations
  • Using two pointers only works for pair sums
3. You are given a list of positive integers and a target sum. You need to determine if there exists a subset of these integers that sums exactly to the target. Which algorithmic approach guarantees an optimal solution for this problem?
easy
A. A greedy algorithm that picks the largest numbers first until the sum is reached or exceeded.
B. A dynamic programming approach that builds a boolean table tracking achievable sums up to the target.
C. A depth-first search that tries all subsets without memoization.
D. A sorting-based two-pointer technique to find pairs that sum to the target.

Solution

  1. Step 1: Understand problem constraints

    The problem requires checking if any subset sums exactly to a target, which is a classic subset sum problem.
  2. Step 2: Identify algorithm that guarantees correctness

    Greedy and two-pointer approaches fail because they do not consider all subsets. DFS without memoization is correct but inefficient. Dynamic programming builds a table of achievable sums, ensuring all subsets are considered efficiently.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    DP tracks all sums up to target -> correct [OK]
Hint: Subset sum requires DP to track achievable sums [OK]
Common Mistakes:
  • Thinking greedy or sorting solves subset sum optimally
4. The following code attempts to solve the integer break problem using bottom-up DP. Which line contains a subtle bug that can cause incorrect results on some inputs?
def integer_break(n):
    dp = [0] * n
    dp[1] = 1
    for i in range(2, n + 1):
        max_product = 0
        for j in range(1, i):
            max_product = max(max_product, max(j, dp[j]) * max(i - j, dp[i - j]))
        dp[i] = max_product
    return dp[n]
medium
A. Line 3: dp[1] = 1 base case initialization
B. Line 2: dp array size is n instead of n+1
C. Line 5: Outer loop range from 2 to n+1
D. Line 7: Using max(j, dp[j]) instead of just dp[j]

Solution

  1. Step 1: Check dp array size

    dp is initialized with size n, but indices up to n are accessed (dp[i], dp[i-j]) which requires size n+1.
  2. Step 2: Consequences of wrong size

    Accessing dp[n] or dp[i-j] when i=n causes index out of range or incorrect results.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    dp array must be size n+1 to safely index up to n [OK]
Hint: Check array size matches max index accessed [OK]
Common Mistakes:
  • Forgetting dp size off-by-one
  • Misplacing base case initialization
5. Suppose the problem is modified so that you want to find the minimum number of perfect squares summing to n, but now each perfect square can only be used at most once. Which of the following changes correctly adapts the algorithm?
hard
A. Keep the same bottom-up DP but iterate squares in increasing order and update dp[i] from dp[i - square] without reuse
B. Use a top-down memoized recursion with a visited set to avoid reusing squares
C. Use a 2D DP array where dp[i][j] represents minimum squares using first j squares to sum to i
D. Change the inner loop to iterate over squares in decreasing order and update dp[i] accordingly

Solution

  1. Step 1: Understand the constraint change

    Limiting each perfect square to be used at most once converts the problem from unbounded to 0/1 knapsack variant, requiring tracking which squares are used.
  2. Step 2: Identify correct DP adaptation

    A 2D DP array dp[i][j] that tracks minimum squares to sum to i using first j squares correctly models the usage constraint. Other options either do not prevent reuse or do not track usage properly.
  3. Step 3: Confirm why other options fail

    Keep the same bottom-up DP but iterate squares in increasing order and update dp[i] from dp[i - square] without reuse still allows reuse implicitly. Use a top-down memoized recursion with a visited set to avoid reusing squares is inefficient and complex. Change the inner loop to iterate over squares in decreasing order and update dp[i] accordingly's order change alone doesn't enforce usage limits.
  4. Final Answer:

    Option C -> Option C
  5. Quick Check:

    0/1 knapsack requires 2D DP to track usage [OK]
Hint: At-most-once usage -> 0/1 knapsack -> 2D DP needed [OK]
Common Mistakes:
  • Trying to reuse unbounded DP
  • Ignoring usage constraints in DP state
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard