Problem statement

https://leetcode.com/problems/day-of-the-week/

Solution

This is really interesting problem, where you need to use two tecniques: dynamic programming and binary search. Let us start our jobs by their starts. Define by dp[k] the maximum gain we can have if we can use only use jobs starting with index k. How we can find dp[k] now and why in the first places we sorted our jobs by starts?

Imagine that we taken job with number k, what we can take next? We need to wait until this job finished, that is to look at jobs[k][1] and find the first job which start more than this number: we use binary search for this with this line temp = bisect_left(S, jobs[k][1]). Finally, our gain will be jobs[k][2] + dp[temp]. Also we have another option: dp[k+1], if we do not take job k. then we can take any jobs from k+1 without restriction.

Notice also that we start from k = n-1 and move to k = 0 in the opposite direction, because to answer dp[k] query we want to already be able to ask queries for dp[>k].

Complexity

Time complexity is O(n * log n), because we do n binary searches. Space complexity is O(n).

Code

import bisect

class Solution:
    def jobScheduling(self, S, E, profit):
        jobs = sorted(list(zip(S, E, profit)))
        S = [i[0] for i in jobs]
        n = len(jobs)
        dp = [0] * (n + 1)
        for k in range(n-1,-1,-1):
            temp = bisect_left(S, jobs[k][1])
            dp[k] = max(jobs[k][2] + dp[temp], dp[k+1])
        return dp[0]

If you have any questions, feel free to ask. If you like solution and explanations, please Upvote!

Remark

Very similar to problem 1751, but here we do not care about how many jobs we take.