Today, I was thinking about a question on Leetcode, Course Schedule III.
The problem first appeared on its weekly online contest. I went to the contest but did not manage to solve it there. Let me rephrase the question here. You have a list of courses and, for each course, you have two numbers: duration and deadline. Duration is the time it takes to complete the course. Deadline is the time you have to finish the course. Then, you have to decide how many courses you are able to take at most, assuming that you can not take two courses at the same time.
Hence, this question is a weird version of the greedy scheduling problems: a hybrid of activity scheduling and deadlines. Activity scheduling has durations but not deadlines. However, this one has deadlines. Deadline scheduling always goes for the earliest possible deadline and it does not work for this problem since if the task with the earliest deadline takes a lot of time that should have been used for more courses, that would not be optimal. For example, if we have
Course 1: duration 10, deadline 10;
Course 2: duration 2, deadline 11;
Course 3: duration 2, deadline 11.
If we go for Course 1, which has the earliest deadline, we waste our time take the long course 1 and the time could have been used to take course 2 and 3, a plan that allows us to finish two courses.
Thus, in activity scheduling, we always go for the shortest activity, so here, what about alway taking the shortest course first? That does not work either.
Course 1: duration 10, deadline 32
Course 2: duration 11, deadline 11
Course 3: duration 11, deadline 22
In this case, if we use our strategy, we will go for Course 1 first since it has the shortest duration. However, that means we can not take Course 2 since, after course 1, we will be at time 10, and there is not enough time to finish course 2 by time 11. However, we should be able to finish all three courses if we take them as course 2, 3, and then 1. Thus, this strategy does not work either.
None of the strategy works. It seems we have to find a “trade-off” between the deadline and the duration. My thinking during the contest ends here.
When I look at the answer, I find this is what the answer does. It checks each course by deadline and keeps track of the selected courses up to the current index. If we can take the next course, we take it; otherwise, we see if we can abandon the longest course taken and take the next course. If the alternative still does not work, that means the new course is longer than any course we have taken before so we do take it.
That is the answer to the problem but why does it work? I need some insights. After thinking about it for a few days, I realize tonight that this is based on a recursive relation between the optimal of a solution and the optimal plus possibly a new course. All courses selected before course k must be finished by the deadline of course k. That is the same for k + 1. We also have to make sure that the total duration is optimized, which means, if there are multiple ways to accomplish the same number of courses before the deadline, we have to make sure that the duration used up is minimum. Hence, two conditions:
- Max courses.
- Min duration for the same number of courses.
Thus, if the new course is good and can be finished by the new deadline, we are good since we have one more course. Otherwise, we still keep the same amount of course so we have to make sure that duration is minimum. The new course, although can not be added, might still be taken by taking away the longest course. Thus, if the new course is shorter than the longest course, we take it and drop the longest current course.
What we must learn is that we should never forget that a lot of things are recursive. We should always make a try to find recursive relations. Greedy, DP, DFS, BFS are all based on recursive relations. The reason why I did not solve this problem during the contest is that I only tried to use those existing solutions to directly solve this problem, instead of going one level further into their fundamentals, recursive relation.