Maximum Profit in Job Scheduling

Description

Maximum Profit in Job Scheduling

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

Approach

• We create a class for better handling
• Create list with job sorted by end time
• Use Tree Map dp to use methods like floorKey which returns greatest key less than equal to key and lastEntry which is mapping associated with greatest key
• Time Complexity: O(n log n)
  Sorting jobs: O(n log n)
  For each job: TreeMap.floorKey and put operations → O(log n)
  Total: O(n log n)
• Space Complexity: O(n)
  jobs list: O(n)
  TreeMap to store at most n entries: O(n)

class Solution {
    private class Job {
        int start, end, profit;
        Job(int s, int e, int p) {
            start = s;
            end = e;
            profit = p;
        }
    }
 
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        List<Job> jobs = new ArrayList<>();
        for (int i = 0; i < startTime.length; i++) {
            jobs.add(new Job(startTime[i], endTime[i], profit[i]));
        }
 
        jobs.sort(Comparator.comparingInt(j -> j.end)); // sort by end time asc
        TreeMap<Integer, Integer> dp = new TreeMap<>();
        dp.put(0,0);
 
        for (Job job: jobs) {
            int prevTime = dp.floorKey(job.start);
            int currProfit = dp.get(prevTime) + job.profit;
 
            if (currProfit > dp.lastEntry().getValue()) {
                dp.put(job.end, currProfit);
            }
        }
 
        return dp.lastEntry().getValue();
    }
}

Primary Approach: Dynamic Programming + Binary Search ($O(N\log N)$ Time, $O(N)$ Space)

Intuition

To solve 1235. Maximum Profit in Job Scheduling, we combine Dynamic Programming with Binary Search (Weighted Interval Scheduling):

1. Sort by End Time: Bundle each job’s startTime, endTime, and profit into an object and sort all jobs in ascending order by their end time.
2. DP Definition: Define dp[i] as the maximum profit achievable using a subset of the first i jobs ($1$-indexed).
3. Transition for Job i - 1:
   • Option 1 (Exclude Job $i-1$): Don’t pick the current job $\to$ dp[i - 1].
   • Option 2 (Include Job $i-1$): Pick the current job $\to$ job.profit + dp[latestCompatible + 1], where latestCompatible is the index of the latest job that ends on or before job.startTime.
4. Binary Search: Since jobs are sorted by endTime, use binary search (upper_bound/floor) to efficiently find latestCompatible in $O(\log N)$ time.

import java.util.Arrays;
 
class Solution {
    static 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]);
        }
 
        // Sort jobs by end time
        Arrays.sort(jobs, (a, b) -> Integer.compare(a.end, b.end));
 
        int[] dp = new int[n + 1];
 
        for (int i = 1; i <= n; i++) {
            int currentProfit = jobs[i - 1].profit;
 
            // Binary search for the last non-overlapping job (end <= start)
            int prevIndex = binarySearch(jobs, i - 1);
 
            int includeProfit = currentProfit + (prevIndex != -1 ? dp[prevIndex + 1] : 0);
            int excludeProfit = dp[i - 1];
 
            dp[i] = Math.max(includeProfit, excludeProfit);
        }
 
        return dp[n];
    }
 
    private int binarySearch(Job[] jobs, int index) {
        int low = 0, high = index - 1;
        int result = -1;
 
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (jobs[mid].end <= jobs[index].start) {
                result = mid;
                low = mid + 1; // Try to find a later compatible job
            } else {
                high = mid - 1;
            }
        }
 
        return result;
    }
}
 

Complexity

• Time Complexity: $O(N\log N)$ — Sorting takes $O(N\log N)$, and $N$ iterations performing $O(\log N)$ binary searches take $O(N\log N)$.
• Space Complexity: $O(N)$ — Space for storing custom Job objects and the dp array.

---

Why i - 1 is Used Everywhere

The core reason for i - 1 is the offset between 1-based Dynamic Programming states and 0-based Java array indexing.

The Index Mapping

• dp Array (1-based, size $n+1$): dp[i] represents the maximum profit achievable considering the first $i$ jobs.
  • dp[0] = Base case (0 jobs considered = 0 profit).
  • dp[1] = Max profit considering the 1st job.
  • dp[n] = Max profit considering all $n$ jobs (our final answer).
• jobs Array (0-based, size $n$): In 0-indexed Java arrays, the $i$-th job is located at index i - 1.

Step-by-Step Breakdown of the Loop

for (int i = 1; i <= n; i++) {
    // STEP 1: Fetch profit of the i-th job
    int currentProfit = jobs[i - 1].profit;
 
    // STEP 2: Find the latest job that ends before jobs[i - 1] starts
    int prevIndex = binarySearch(jobs, i - 1);
 
    // STEP 3: Profit if we INCLUDE jobs[i - 1]
    int includeProfit = currentProfit + (prevIndex != -1 ? dp[prevIndex + 1] : 0);
 
    // STEP 4: Profit if we EXCLUDE jobs[i - 1]
    int excludeProfit = dp[i - 1];
 
    // STEP 5: Pick the best of both choices for dp[i]
    dp[i] = Math.max(includeProfit, excludeProfit);
}
 

1. currentProfit = jobs[i - 1].profit
   To evaluate the $i$-th job, we access jobs[i - 1] because the 1st job is at jobs[0], the 2nd job is at jobs[1], etc.
2. prevIndex = binarySearch(jobs, i - 1)
   Passes i - 1 (the 0-based index of the current job) to binary search to locate the latest compatible non-overlapping job.
3. includeProfit = currentProfit + (prevIndex != -1 ? dp[prevIndex + 1] : 0)
   If we INCLUDE the current job:
   • We earn its currentProfit.
   • prevIndex is the 0-based index returned by binary search (e.g., prevIndex = 2 means the 3rd job in the array).
   • Because dp uses 1-based counting, the maximum profit for the first prevIndex + 1 jobs is stored at dp[prevIndex + 1].
   • If prevIndex == -1 (no compatible prior job exists), add 0.
4. excludeProfit = dp[i - 1]
   If we EXCLUDE the current job, the maximum profit is simply the maximum profit achieved from the first i - 1 jobs, which is stored in dp[i - 1].
5. dp[i] = Math.max(includeProfit, excludeProfit)
   Takes the maximum between taking or skipping the current job and stores it in dp[i].

Why binarySearch Starts with high = index - 1

private int binarySearch(Job[] jobs, int index) {
    int low = 0, high = index - 1; // <--- Why high = index - 1?
    int result = -1;
    ...
 

1. Excludes the Current Job: index is the position of the job we are evaluating. A job cannot be non-overlapping with itself, so we must strictly search among jobs before index.
2. Preserves the Sorted Range: The jobs array is sorted by endTime. Any job that ends before jobs[index].start **must appear at an index smaller than index** (i.e., from index 0 to index - 1).
3. Prevents Redundant Lookups: Setting high = index - 1 guarantees that mid will never reach index or beyond, restricting binary search exclusively to earlier jobs.

---

Alternative Approach: Dynamic Programming + TreeMap ($O(N\log N)$ Time, $O(N)$ Space)

Intuition

Instead of maintaining an explicit 1D array, store optimal (endTime, maxProfit) pairs inside a TreeMap:

1. Sort jobs by endTime.
2. Insert base state (0, 0) into dp (TreeMap<Integer, Integer>).
3. For each job (start, end, profit):
   • Query dp.floorEntry(start) to get the maximum profit achievable up to start.
   • Calculate total profit if taking this job: floorEntry.getValue() + profit.
   • If this new profit strictly exceeds dp.lastEntry().getValue(), record dp.put(end, totalProfit).

import java.util.Arrays;
import java.util.TreeMap;
 
class Solution {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        int[][] jobs = new int[n][3];
        for (int i = 0; i < n; i++) {
            jobs[i] = new int[]{startTime[i], endTime[i], profit[i]};
        }
 
        // Sort by end time
        Arrays.sort(jobs, (a, b) -> Integer.compare(a[1], b[1]));
 
        // Key = end time, Value = max profit at or before this end time
        TreeMap<Integer, Integer> dp = new TreeMap<>();
        dp.put(0, 0);
 
        for (int[] job : jobs) {
            int start = job[0], end = job[1], p = job[2];
 
            int totalProfit = dp.floorEntry(start).getValue() + p;
 
            if (totalProfit > dp.lastEntry().getValue()) {
                dp.put(end, totalProfit);
            }
        }
 
        return dp.lastEntry().getValue();
    }
}
 

Complexity

• Time Complexity: $O(N\log N)$ — Sorting takes $O(N\log N)$ and performing $N$ TreeMap lookups/insertions takes $O(N\log N)$.
• Space Complexity: $O(N)$ — Space needed for $O(N)$ entries in TreeMap.

---

Key Interview Discussion Points

• Non-Overlapping Edge Case: If job A ends at $X$ and job B starts at $X$, they do not overlap. Ensure the binary search/lookup checks for jobs[mid].end <= jobs[i].start (inclusive inequality).
• Why Sort by End Time? Sorting by endTime allows past subproblems (0 ... i-1) to represent finalized maximum profits for time ranges ending before or at jobs[i].start.

---

Easy Memory Rule

“Sort by End Time $\to$ Choice: dp[i-1] vs. profit + dp[BinarySearch(start)]!”