Scale Engineer

Maximum Profit in Job Scheduling

Hard
#1153Time: O(n * 2^n). The recursion tree can have up to 2^n nodes. In each node, we might do a linear scan to find the next job, which takes O(n) time. Sorting takes an initial O(n log n). The overall complexity is dominated by the exponential nature of the recursion.Space: O(n), for the recursion call stack depth in the worst case.17 companies
Patterns
Dynamic Programming
Algorithms
Binary SearchSorting
Data structures
Array
Companies
AirbnbDoorDashFlipkartPayPal

Prompt

We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i].

You're given the startTime, endTime and profit arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range.

If you choose a job that ends at time X you will be able to start another job that starts at time X.

 

Example 1:

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120
Explanation: The subset chosen is the first and fourth job. 
Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.

Example 2:

Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
Output: 150
Explanation: The subset chosen is the first, fourth and fifth job. 
Profit obtained 150 = 20 + 70 + 60.

Example 3:

Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
Output: 6

 

Constraints:

  • 1 <= startTime.length == endTime.length == profit.length <= 5 * 104
  • 1 <= startTime[i] < endTime[i] <= 109
  • 1 <= profit[i] <= 104

Approaches

3 approaches with complexity analysis and trade-offs.

This approach explores all possible valid subsets of jobs. For each job, we make a decision: either to include it in our set or to skip it. This generates a decision tree of possibilities. We then find the path in this tree that yields the maximum total profit. While simple to understand, it is highly inefficient.

Algorithm

  • Create a Job class to encapsulate startTime, endTime, and profit.
  • Create an array of Job objects from the input arrays.
  • Sort the Job array based on startTime to process jobs in chronological order.
  • Define a recursive function solve(index) that calculates the maximum profit from jobs index to n-1.
  • In solve(index):
    • Base Case: If index is out of bounds, return 0.
    • Recursive Step: Explore two choices for jobs[index]:
      1. Exclude: The profit is solve(index + 1).
      2. Include: The profit is jobs[index].profit plus the result of solve(nextIndex), where nextIndex is the first job that starts after jobs[index] ends.
    • Return the maximum of the two choices.
  • The initial call is solve(0).

Walkthrough

The brute-force method systematically checks every combination of jobs. We can model this using recursion.

First, we combine the startTime, endTime, and profit arrays into a single structure, a Job object, for easier handling. To make the decision process more structured, we sort these jobs based on their startTime.

A recursive function, let's call it findMaxProfit(index), is the core of this approach. This function calculates the maximum profit obtainable from the sub-array of jobs starting from index.

For any given job[index], we face two choices:

  1. Skip the job: We don't take jobs[index]. The maximum profit is then whatever we can make from the remaining jobs, which is found by recursively calling findMaxProfit(index + 1).
  2. Take the job: We add jobs[index].profit to our total. Since we cannot take any overlapping jobs, we must then find the first subsequent job that starts at or after the current job's endTime. Let's say this is at nextIndex. We then add the result of findMaxProfit(nextIndex) to our current job's profit.

The function returns the maximum profit from these two choices. The process starts with findMaxProfit(0).

class Solution {    class Job {        int start, end, profit;        Job(int start, int end, int profit) {            this.start = start;            this.end = end;            this.profit = profit;        }    }     public 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, (a, b) -> a.start - b.start);        return findMaxProfit(jobs, 0);    }     private int findMaxProfit(Job[] jobs, int index) {        if (index >= jobs.length) {            return 0;        }         // Option 1: Exclude current job        int profit1 = findMaxProfit(jobs, index + 1);         // Option 2: Include current job        // Find the next non-overlapping job by linear scan        int nextIndex = jobs.length;        for (int j = index + 1; j < jobs.length; j++) {            if (jobs[j].start >= jobs[index].end) {                nextIndex = j;                break;            }        }        int profit2 = jobs[index].profit + findMaxProfit(jobs, nextIndex);         return Math.max(profit1, profit2);    }}

Complexity

Time

O(n * 2^n). The recursion tree can have up to 2^n nodes. In each node, we might do a linear scan to find the next job, which takes O(n) time. Sorting takes an initial O(n log n). The overall complexity is dominated by the exponential nature of the recursion.

Space

O(n), for the recursion call stack depth in the worst case.

Trade-offs

Pros

  • Simple to conceptualize and implement.

  • Directly translates the problem statement into a recursive structure.

Cons

  • Extremely inefficient due to its exponential time complexity.

  • Will result in a 'Time Limit Exceeded' error on most platforms for the given constraints.

  • Performs a large number of redundant computations for the same subproblems.

Solutions

class Solution {private  int[][] jobs;private  int[] f;private  int n;public  int jobScheduling(int[] startTime, int[] endTime, int[] profit) {    n = profit.length;    jobs = new int[n][3];    for (int i = 0; i < n; ++i) {      jobs[i] = new int[]{startTime[i], endTime[i], profit[i]};    }    Arrays.sort(jobs, (a, b)->a[0] - b[0]);    f = new int[n];    return dfs(0);  }private  int dfs(int i) {    if (i >= n) {      return 0;    }    if (f[i] != 0) {      return f[i];    }    int e = jobs[i][1], p = jobs[i][2];    int j = search(jobs, e, i + 1);    int ans = Math.max(dfs(i + 1), p + dfs(j));    f[i] = ans;    return ans;  }private  int search(int[][] jobs, int x, int i) {    int left = i, right = n;    while (left < right) {      int mid = (left + right) >> 1;      if (jobs[mid][0] >= x) {        right = mid;      } else {        left = mid + 1;      }    }    return left;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem