Problem statement

https://leetcode.com/problems/course-schedule-iii/

Solution

The clue idea, without which this problem is unsolvable, is then we always can change order of taken courses, such that their end times are increasing. It does not mean, that we need to take all the courses one by one, but there will always be order. For example if we have courses 1,2,3,4, we can take 1,2,4 or 1,3,4 or something else, but it always will be subsequence of 1,2,3,4. Note, that there is still O(2^n) options, so we are not able to check them all, so we need some additional idea.

One possible solution is to use dp with states (i, time), where i means that we already considered first i courses (we take some of them and did not take some of them) and time means what moment of time it is now. Then on each step we can have two options: take course number i and do not take it. Overall time and space complexity is O(n * d), where n is number of courses and d is maximum value of days we have.

Another approach is to try to use greedy approach, when we add new course. Let us consider courses one by one and our invariant after k courses will be pair (N_k, T_k), where N_k is the maximum number of courses we can take and T_k is minimum time spend for taken courses. So, what happened, when we add (k+1)th course? If it fits, we just add it, so N_{k+1} = N_k + 1 and T_{k+1} = T_k + l_{k+1}, where l_{k+1} is length of course number k+1. If it not fits, then it means, it is not possible to take N_k+1 courses and we can take only N_k. However, we need to minimize T_{k+1} as well! So we have to get rid of one of the courses, such that we can fit N_k of them.

So, we already know that we can take at most N_k courses among first k + 1 courses, the question is now which ones should be choose? The answer is that we need to choose courses with the smallest possible durations. As we sorted our courses by end times, on each step the set of avaliable courses we can take can only increase. So, we add courses one by one and if it happens that we can not fit them all, we need to get rid of the most heavy ones: with biggest duration.

Complexity

Time complexity is O(n*log n), space is O(n).

Code

class Solution:
    def scheduleCourse(self, courses):
        heap, time = [], 0
        for t, end in sorted(courses, key=lambda x: x[1]):
            time += t
            heapq.heappush(heap, -t)
            if time > end:
                nt = heapq.heappop(heap)
                time += nt
        return len(heap)

Remark

If we do not use queue and just find each time longest course among n, we have O(n^2) complexity. We can optimize it to O(n * m), where m is our total number of courses found, if we take into account that we need to look among only taken courses, not all of them.