Problem Description

You are given three arrays of equal length: startTime, endTime, and profit, where each element represents a job. Specifically, the i-th job starts at startTime[i], ends at endTime[i], and yields a profit of profit[i] if taken.

You can choose any subset of these jobs to schedule, but you cannot select two jobs that overlap in time (that is, a job cannot start before another job ends). Your goal is to select a subset of non-overlapping jobs to maximize the total profit.

Constraints:

• Each job can be used at most once.
• There may be multiple jobs with the same start or end time.
• At least one valid solution exists for any input.
• You must find the maximum total profit possible.

Thought Process

At first glance, this problem looks similar to other scheduling problems, like the classic "activity selection" or "weighted interval scheduling." A brute-force approach would be to try every possible subset of jobs, check if they overlap, and calculate the profit for each valid subset. However, with up to 5,000 jobs, this approach is infeasible, as the number of subsets grows exponentially.

Instead, we can look for patterns:

• If we sort jobs by their end time, we can process them in a way that always considers the earliest finishing jobs first.
• For each job, we have two choices: include it (and add its profit to the best solution that doesn't overlap with it), or skip it.
• We need an efficient way to find the last job that doesn't overlap with the current one. This hints at a binary search or dynamic programming approach.

Solution Approach

We'll use a dynamic programming approach optimized with binary search. Here's how:

1. Combine and Sort Jobs: Create a list of jobs where each job is a tuple of (start, end, profit). Sort this list by end time. Sorting ensures we always process the earliest finishing jobs first, which is essential for dynamic programming.
2. Dynamic Programming Table: We'll keep a DP array (or map) where each entry represents the maximum profit achievable up to a certain job.
3. For Each Job:
   • Use binary search to find the last job that ends before the current job starts (i.e., the latest non-conflicting job).
   • Calculate the profit if we take the current job: add its profit to the DP value of the last non-conflicting job.
   • Update the DP table: the maximum of (profit if we take the job, profit if we skip it).
4. Return the Maximum Profit: The last value in the DP table will be the answer.

Why these choices?

• Sorting by end time makes the problem easier to manage, as we always know which jobs are compatible.
• Binary search allows us to efficiently find the last non-overlapping job, reducing the time complexity.
• Dynamic programming ensures we build up the solution efficiently from smaller subproblems.

Example Walkthrough

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

Step 1: Combine and Sort Jobs
Jobs (start, end, profit) after sorting by end time:

• (1, 3, 50)
• (2, 4, 10)
• (3, 5, 40)
• (3, 6, 70)

Step 2: DP Iterations

• Job 0: No previous jobs. Take profit = 50.
• Job 1: Overlaps with job 0, so max(50, 10) = 50.
• Job 2: Last non-overlapping job is job 0 (ends at 3, current starts at 3). Profit = 50 + 40 = 90. Max(50, 90) = 90.
• Job 3: Last non-overlapping job is job 0 (ends at 3, current starts at 3). Profit = 50 + 70 = 120. Max(90, 120) = 120.

Explanation: The optimal solution is to take jobs 0 and 3, for a total profit of 50 + 70 = 120.

Code Implementation

from bisect import bisect_right

class Solution:
    def jobScheduling(self, startTime, endTime, profit):
        jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])
        n = len(jobs)
        dp = [0] * (n + 1)
        ends = [job[1] for job in jobs]

        for i in range(1, n + 1):
            s, e, p = jobs[i - 1]
            # Find the last job that ends before the current job starts
            idx = bisect_right(ends, s, 0, i - 1)
            dp[i] = max(dp[i - 1], dp[idx] + p)
        return dp[n]
      

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        int n = startTime.size();
        vector<tuple<int,int,int>> jobs;
        for (int i = 0; i < n; ++i)
            jobs.emplace_back(startTime[i], endTime[i], profit[i]);
        sort(jobs.begin(), jobs.end(), [](auto& a, auto& b) {
            return get<1>(a) < get<1>(b);
        });
        vector<int> dp(n+1, 0);
        vector<int> ends;
        for (auto& job : jobs) ends.push_back(get<1>(job));
        for (int i = 1; i <= n; ++i) {
            int s = get<0>(jobs[i-1]), p = get<2>(jobs[i-1]);
            auto it = upper_bound(ends.begin(), ends.begin() + i - 1, s);
            int idx = distance(ends.begin(), it);
            dp[i] = max(dp[i-1], dp[idx] + p);
        }
        return dp[n];
    }
};
      

import java.util.*;

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][0] = startTime[i];
            jobs[i][1] = endTime[i];
            jobs[i][2] = profit[i];
        }
        Arrays.sort(jobs, Comparator.comparingInt(a -> a[1]));
        int[] dp = new int[n + 1];
        int[] ends = new int[n];
        for (int i = 0; i < n; i++) ends[i] = jobs[i][1];
        for (int i = 1; i <= n; i++) {
            int s = jobs[i-1][0], p = jobs[i-1][2];
            int idx = Arrays.binarySearch(ends, 0, i - 1, s);
            if (idx < 0) idx = -idx - 1;
            dp[i] = Math.max(dp[i-1], dp[idx] + p);
        }
        return dp[n];
    }
}
      

var jobScheduling = function(startTime, endTime, profit) {
    let n = startTime.length;
    let jobs = [];
    for (let i = 0; i < n; i++) {
        jobs.push([startTime[i], endTime[i], profit[i]]);
    }
    jobs.sort((a, b) => a[1] - b[1]);
    let dp = new Array(n + 1).fill(0);
    let ends = jobs.map(job => job[1]);
    for (let i = 1; i <= n; i++) {
        let s = jobs[i-1][0], p = jobs[i-1][2];
        // Binary search for last non-conflicting job
        let left = 0, right = i - 1;
        while (left < right) {
            let mid = Math.floor((left + right) / 2);
            if (ends[mid] <= s) left = mid + 1;
            else right = mid;
        }
        let idx = (ends[left] <= s) ? left + 1 : left;
        dp[i] = Math.max(dp[i-1], dp[idx] + p);
    }
    return dp[n];
};
      

Time and Space Complexity

Brute-force: The brute-force approach would try every subset of jobs, which is O(2^n) time and space, and is infeasible for large n.

Optimized DP + Binary Search:

• Sorting the jobs: O(n \log n)
• For each job, binary search for the last non-overlapping job: O(\log n) per job, for n jobs is O(n \log n)
• Overall time complexity: O(n \log n)
• Space complexity: O(n) for the DP array and auxiliary arrays

Summary

The "Maximum Profit in Job Scheduling" problem is a classic example of weighted interval scheduling, where we need to select non-overlapping jobs to maximize profit. By sorting jobs by end time, using dynamic programming to build up solutions, and binary search to quickly find compatible jobs, we achieve an efficient O(n \log n) solution. The key insights are recognizing the structure of the problem and using the right data structures for performance, making the solution both elegant and practical.