n different online courses numbered from
n. Each course has some duration(course length)
t and closed on
dth day. A course should be taken continuously for
t days and must be finished before or on the
dth day. You will start at the
n online courses represented by pairs
(t,d), your task is to find the maximal number of courses that can be taken.
Input: [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]] Output: 3 Explanation: There're 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.
The most naive solution will be to consider every possible permutation of the given courses and to try to take as much courses as possible by taking the courses in a serial order in every permutation. We can find out the maximum number of courses that can be taken from out of values obtained from these permutations.\n
Time complexity : . A total of permutations are possible for the array of length . For every permutation, we scan over the elements of the permutation to find the number of courses that can be taken in each case.\n
Space complexity : . Each permutation needs space.\n
Before we move on to the better approaches, let\'s discuss one basic idea to solve the given problem. Suppose, we are considering only two courses and . Let\'s assume . Now, we\'ll look at the various relative values which and can take, and which course should be taken first in each of these cases. In all the cases, we assume that the course\'s duration is always lesser than its end day i.e. and .\n
From the above example, we can conclude that it is always profitable to take the course with a smaller end day prior to a course with a larger end day. This is because, the course with a smaller duration, if can be taken, can surely be taken only if it is taken prior to a course with a larger end day.\n
Based on this idea, firstly, we sort the given array based on their end days. Then, we try to take the courses in a serial order from this sorted array.\n
In order to solve the given problem, we make use of a recursive function
schedule(courses, i, time) which returns the maximum number of courses that can be taken starting from the course(starting from 0), given the time aleady consumed by the other courses is , i.e. the current time is , given a array as the schedule.
Now, in each function call to
schedule(courses, i, time), we try to include the current course in the taken courses. But, this can be done only if . Here, refers to the duration of the course and refers to the end day of the course.
If the course can be taken, we increment the number of courses taken and obtain the number of courses that can be taken by passing the updated time and courses\' index. i.e. we make the function call
schedule(courses, i + 1, time + duration_i). Let\'s say, we store the number of courses that can be taken by taking the current course in variable.
Further, for every current course, we also leave the current course, and find the number of courses that can be taken thereof. Now, we need not update the time, but we need to update the courses\' index. Thus, we make the function call,
schedule(courses, i + 1, time). Let\'s say, we store the count obtained in variable.
While returning the number of courses at the end of each function call, we return the maximum value out of and .\n
Thus, the function call
schedule(courses, 0, 0) gives the required result.
In order to remove this redundancy, we make use of a memoization array , such that is used to store the result of the function call
schedule(courses, i, time). Thus, whenever the same function call is made again, we can return the result directly from the array. This helps to prune the search space to a great extent.
Time complexity : . array of size x is filled once. Here, refers to the number of courses in the given array and refers to the maximum value of the end day from all the end days in the array.\n
Space complexity : . array of size x is used.\n
For the current approach, the idea goes as follows. As discussed in the previous approaches, we need to sort the given array based on the end days. Thus, we consider the courses in the ascending order of their end days. We keep a track of the current time in a variable. Along with this, we also keep a track of the number of courses taken till now in variable.\n
For each course being considered currently(let\'s say course), we try to take this course. But, to be able to do so, the current course should end before its corresponding end day i.e. . Here, refers to the duration of the course and refers to the end day of the course.\n
If this course can be taken, we update the current time to and also increment the current value to indicate that one more course has been taken.\n
But, if we aren\'t able to take the current course i.e. , we can try to take this course by removing some other course from amongst the courses that have already been taken. But, the current course can fit in by removing some other course, only if the duration of the course() being removed is larger than the current course\'s duration, i.e. .\n
We are sure of the fact that by removing the course, we can fit in the current course, because, was already fitting in the duration available till now. Since, , the current course can surely take its place. Thus, we look for a course from amongst the taken courses having a duration larger than the current course.\n
But why are we doing this replacement? The answer to this question is as follows. By replacing the course, with the course of a relatively smaller duration, we can increase the time available for upcoming courses to be taken. An extra time can be made available by doing so.\n
Now, for this saving in time to be maximum, the course taken for the replacement should be the one with the maximum duration. Thus, from amongst the courses that have been taken till now, we find the course having the maximum duration which should be more than the duration of the current course(which can\'t be taken).\n
Let\'s say, this course be called as . Thus, now, a saving of can be achived, which could help later in fitting in more courses to be taken.\n
If such a course, , is found, we remove this course from the taken courses and consider the current course as taekn. We also mark this course with to indicate that this course has not been taken and should not be considered in the future again for replacement.\n
But, if such a course isn\'t found, we can\'t take the current course at any cost. Thus, we mark the current course with to indicate that the current course has not been taken.\n
At the end, the value of gives the required result.\n
The following animation illustrates the process.\n
Time complexity : . We iterate over the array of size once. For every element currently considered, we could scan backwards till the first element, giving complexity. Sorting the array takes time for array.\n
Space complexity : . Constant extra space is used.\n
In the last approach, we\'ve seen that, in the case of current course which can\'t be taken direclty, i.e. for , we need to traverse back in the array till the beginning to find a course with the maximum duration which is larger than the current course\'s duration. This backward traversal also goes through the courses which aren\'t taken and thus, can\'t be replaced, and have been marked as .\n
We can bring in some optimization here. For this, we should search among only those courses which have been taken(and not the ones which haven\'t been taken).\n
To do so, as we iterate over the array, we also keep on updating it, such that the first number of elements in this array now correspond to only those number of courses which have been taken till now.\n
Thus, whenever we update the to indicate that one more course has been taken, we also update the entry to \nreflect the current course that has just been taken.\n
Whenever, we find a course for which , we find a course from only amongst these first number of courses in the array, which indicate the courses that have been taken till now.\n
Also, instead of marking this course with a , we can simply replace this course with the current course. Thus, the first courses still reflect the courses that have been taken till now.\n\n
Time complexity : . We iterate over a total of elements of the array. For every element, we can traverse backwards upto atmost (final value) number of elements.\n
Space complexity : . Constant extra space is used.\n
In the last approach, we updated the array itself so that the first elements indicate the number of courses that have been taken till now. If it is required to retain the array as such, we can do the same job by maintaining a separate list which is the list of those courses that have been taken till now.\n
Thus, to find the course, we need to search in this list only. Further, when replacing this course with the current course, we can replace this course in the list with current course directly. The rest of the method remains the same as the last approach.\n\n
Time complexity : . We iterate over a total of elements of the array. For every element, we can traverse over atmost number of elements. Here, refers to the final length of the .\n
Space complexity : . The can contain atmost courses.\n
This approach is inspired by @stomach_ache\n
In the last few approaches, we\'ve seen that we needed to traverse over the courses which have been taken to find the course(with the maximum duration) which can be replaced by the current course(if it can\'t be taken directly). These traversals can be saved, if we make use of a Priority Queue, (which is implemented as a Max-Heap) which contains the durations of all the courses that have been taken till now.\n
The iteration over the sorted remains the same as in the last approaches. Whenver the current course( course) can be taken(), it is added to the and the value of the current time is updated to .\n
If the current course can\'t be taken directly, as in the previous appraoches, we need to find a course whose duration is maximum from amongst the courses taken till now. Now, since we are maintaing a Max-Heap, , we can obtain this duration directly from this . If the duration , we can replace the course, with the current one.\n
Thus, we remove the from the and add the current course\'s duration to the . We also need to make proper adjustments to the to account for this replacement done.\n
At the end, the number of elements in the represent the number of courses that have been taken till now.\n\n
Time complexity : . At most elements are added to the . Adding each element is followed by heapification, which takes time.\n
Space complexity : . The containing the durations of the courses taken can have atmost elements\n
Analysis written by: @vinod23\n