Leetcode - 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.

Ideas

• At a given time, we want to choose the interval that gives us the maximum profit, therefore, we have a choice that we can make. We can also recognize that the max profit at index i is the max profit at index i+1. This means we want to use Dynamic Programming
• We have three parallel arrays. Which we want to zip into a tuple of (start, end, profit) using pythons built in zip method. Then we can just cast it as a list
• Our state is the current index we are at
• Our base case is returning 0 if i goes out of range
• From our dfs, we return our current max profit
• We have two choices:
  • we take the current job
  • we skip the current job
• If we take the current job, we want to figure out the index of the next job we can run which is the first job whose start time is ≥ our current end time
• we do a binary search on our zipped object to find this index (which is the l pointer after we shrink the search space completely)
• Then we set first to our current profit + dp(l)
• Otherwise we set second to dp(i+i) to skip the current interval
• We return the max of these two
• We also want to cache our results

Solution