LC 0630 [H] Course Schedule III - ALawliet/algorithms GitHub Wiki

Sort all the courses by their ending time. When considering the first K courses, they all end before end. A necessary and sufficient condition for our schedule to be valid, is that (for all K), the courses we choose to take within the first K of them, have total duration less than end.

For each K, we will greedily remove the largest-length course until the total duration start is <= end. To select these largest-length courses, we will use a max heap. start will maintain the loop invariant that it is the sum of the lengths of the courses we have currently taken.

Clearly, this greedy choice makes the number of courses used maximal for each K. When considering potential future K, there's never a case where we preferred having a longer course to a shorter one, so indeed our greedy choice dominates all other candidates.

---

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.

---

class Solution:
    def scheduleCourse(self, A):
        max_heap = [] # biggest duration courses
        start = 0

        A.sort(key=lambda x: x[1]) # sort by end
        
        for t, end in A:
            start += t # total duration
            heappush(max_heap, -t)
            while start > end:
                start += heappop(max_heap)

        return len(max_heap) # most smallest duration courses