There are n different online courses numbered from 1 to n. You are given an array courses where courses[i] = [durationi, lastDayi] indicate that the ith course should be taken continuously for durationi days and must be finished before or on lastDayi.
You will start on the 1st day and you cannot take two or more courses simultaneously.
Return the maximum number of courses that you can take.
Example 1:
Input: courses = [[100,200],[200,1300],[1000,1250],[2000,3200]] Output: 3 Explanation: There are totally 4 courses, but you can take 3 courses at most: First, take the 1st course, it costs 100 days so you will finish it on the 100th day, and ready to take the next course on the 101st day. Second, take the 3rd course, it costs 1000 days so you will finish it on the 1100th day, and ready to take the next course on the 1101st day. Third, take the 2nd course, it costs 200 days so you will finish it on the 1300th day. The 4th course cannot be taken now, since you will finish it on the 3300th day, which exceeds the closed date. Example 2:
Input: courses = [[1,2]] Output: 1 Example 3:
Input: courses = [[3,2],[4,3]] Output: 0
There is no dependency between courses, so we can take them in any order. imagine we are in a the timeline. Each line has a deadline and a length. What we want to do is trying put as much as possible lines in the timeline. We can sort the lines by deadline. Then we can try to put the lines in the timeline one by one. If we can put a line in the timeline, we put it. If we can't, we can either drop it or replace it with a longer line we have put before. We can prove that this is always the best strategy. It seems like a greedy solution. But how can we do this "overlap" check quickly? And shall we put it eralier or later...hard to think about.
Let me see the std's soluton. First still sort the lines by deadline. Then we can use a priority queue to store the lines we have put in the timeline. The priority queue is sorted by the length of the lines. Each time we put a line in the timeline, we add its length to the timeline length. If the timeline length exceeds the deadline, we can drop the longest line in the priority queue. If the timeline length is still larger than the deadline, we drop the current line. Otherwise, we keep the current line in the priority queue. We can prove that this is always the best strategy. The priority queue is implemented by a max heap. So the time complexity is O(nlogn). so we just put it at the 'as early as possible' and then if even if we put it 'as early as possible', we still cannot schedule them. We just be greedy, compare it with the peek of heap (longest one). If current one is smaller, definitly, it's better to take the current one.