MANG Problem #35: Maximum Profit in Job Scheduling (Hard)

1. Problem Statement

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.

2. Approach: Sort + DP + Binary Search

This is an optimization over standard 0/1 Knapsack for intervals. For every job, we can either:

1. Skip it: The profit is the same as the maximum profit up to the previous job.
2. Take it: The profit is this job's profit + the maximum profit from non-overlapping jobs before it.

To do this efficiently:

1. Sort: Sort all jobs by their end time.
2. DP Array: dp[i] stores the max profit using a subset of the first i jobs.
3. Binary Search: To quickly find the last non-overlapping job before job i, we use binary search (since they are sorted by end time).

3. Java Implementation

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) {
    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]);
    }
    
    // 1. Sort by end time
    Arrays.sort(jobs, (a, b) -> a.end - b.end);
    
    // dp[i] stores max profit up to job i
    int[] dp = new int[n];
    dp[0] = jobs[0].profit;
    
    for (int i = 1; i < n; i++) {
        // Option 1: Skip current job
        int skipProfit = dp[i - 1];
        
        // Option 2: Take current job
        int takeProfit = jobs[i].profit;
        int latestNonConflict = binarySearch(jobs, i);
        if (latestNonConflict != -1) {
            takeProfit += dp[latestNonConflict];
        }
        
        dp[i] = Math.max(skipProfit, takeProfit);
    }
    
    return dp[n - 1];
}

// Find the latest job that ends <= current job's start time
private int binarySearch(Job[] jobs, int currentIndex) {
    int low = 0, high = currentIndex - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (jobs[mid].end <= jobs[currentIndex].start) {
            if (jobs[mid + 1].end <= jobs[currentIndex].start) {
                low = mid + 1; // Can we find a later one?
            } else {
                return mid;
            }
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

4. 5-Minute "Video-Style" Walkthrough

1. The "Aha!" Moment: If you sort jobs by end time, the problem becomes a sequence of choices. By the time you process job i, you already know the absolute best profit you could make ending before job i.
2. The Fast Lookup: Without binary search, finding the compatible previous job takes $O(N)$, making the overall solution $O(N^2)$. Since jobs are sorted by end time, finding the latest end time $\le$ current start time takes $O(\log N)$.
3. The State Array: dp[i] monotonically increases. It means "The absolute best I can do considering jobs 0 through i".

5. Interview Discussion

• Interviewer: "Can this be solved using a TreeMap?"
• You: "Yes! A TreeMap<Integer, Integer> mapping endTime -> maxProfit can simplify the code. We use floorEntry(startTime) to find the best previous profit. The complexity remains $O(N \log N)$."