LeetCode 1235. Maximum Profit in Job Scheduling

Question

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

Source: https://leetcode.com/problems/maximum-profit-in-job-scheduling/

Solution

First, jobs are obviously a kind of interval. Each job has start and end. So as a common operation for solving interval problems, we need to sort intervals. And in this problem, we care more about the end time of jobs because the end time limits the selection of next job. Thus, we choose to sort jobs by end time.

Then, this problem is also a scheduling problem. If we try to enumerate all possible schedules, the time complexity will be unacceptably high. So, natually we think of Dynamic Programming, which caches the result of subproblems.

Each DP element represents the max profit when that schedule ends at time e. The state transition equation is DP[new_end] = curr_job.profit + DP[end_just_before_curr_start] . Thus, we need to search a previous DP element whose end is before the start of current job. Binary search is much faster than linear search, that is one reason why we use TreeMap.

Also, we use greedy thought in following solution. According to the state transition equation, a new schedule with higher end has its meaning only if its profit is also higher. If not, it makes no good but intervene the binary search. So schedules is monotonic. If one entry in schedules has a higher end than another entry, it must has a higher profit.

static class Job {
    public int start;
    public int end;
    public int profit;

    public Job(int s, int e, int p) {
        this.start = s;
        this.end = e;
        this.profit = p;
    }
}

// Time Complexity: O(n*log(n))
// the sort process costs O(n*log(n)), each search in TreeMap costs O(log(n))
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]));
    }
    // sort by the end time, ascending
    Collections.sort(jobs, new Comparator<Job>() {
        @Override
        public int compare(Job o1, Job o2) {
            return o1.end - o2.end;
        }
    });

    // key-value <e, p> means before end time e, the max profit we can get is p
    // we deduce kv pairs from low end to high end by DP
    // like a "non-fixed-size" DP
    // it has 3 features: binary search, DP, monotonic
    TreeMap<Integer, Integer> schedules = new TreeMap<>();
    schedules.put(0, 0);
    // DP, enumerate each schedule ending with each job
    for (Job job : jobs) {
        int currProfit = schedules.floorEntry(job.start).getValue() + job.profit;
        // during traversal, the end of job becomes higher and higher
        // greedy thought, a new schedule with higher end has its meaning only if its profit is also higher
        // compare with the last kv value, because we sort jobs by end time
        if (currProfit > schedules.lastEntry().getValue()) {
            schedules.put(job.end, currProfit);
        }
    }
    return schedules.lastEntry().getValue();
}