Maximum Profit in Job Scheduling

Leetcode Problem 1235: Maximum Profit in Job Scheduling

Problem Summary

There are n jobs, where job i runs from startTime[i] to endTime[i] and yields profit[i]. Given the three arrays, return the maximum profit obtainable by choosing a subset of jobs with no two overlapping in time. A job ending at time X does not conflict with another job starting at time X. There are up to 5 x 10^4 jobs, times are positive integers up to 10^9, and each profit is up to 10^4.

This is a weighted interval scheduling problem, a one-dimensional DP over a sorted timeline rather than a spatial grid. After sorting jobs by start time, the state is the best profit considering jobs from an index onward, and at each job we choose to skip it or take it. Taking a job jumps to the first job whose start time is at least the current job's end time, located with a binary search over the sorted start times.

Techniques

Array
Binary Search
Dynamic Programming
Sorting

Solution

function jobScheduling(startTime: number[], endTime: number[], profit: number[]): number {
    const n = startTime.length;
    const jobs = startTime.map((s, i) => ({ start: s, end: endTime[i], profit: profit[i] }));
    jobs.sort((a, b) => a.start - b.start);
    const memo = new Array(n).fill(-1);

    function nextCompatible(target: number, from: number): number {
        let left = from;
        let right = n;
        while (left < right) {
            const mid = (left + right) >> 1;
            if (jobs[mid].start < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    function dfs(i: number): number {
        if (i >= n) {
            return 0;
        }
        if (memo[i] !== -1) {
            return memo[i];
        }
        const skip = dfs(i + 1);
        const take = jobs[i].profit + dfs(nextCompatible(jobs[i].end, i + 1));
        memo[i] = Math.max(skip, take);
        return memo[i];
    }

    return dfs(0);
}