Differences

This shows you the differences between two versions of the page.

--- scratch_algo [2020/08/28 20:40]
127.0.0.1 external edit
+++ scratch_algo [2020/08/28 21:17] (current)
@@ Line 44: / Line 44: @@
 [[https://leetcode.com/problems/course-schedule-iii/solution/|Leetcode 630]].
+**There are ''n'' different online courses numbered from ''1'' to ''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 1st day.
+Given ''n'' online courses represented by pairs ''(t,d)'', your task is to find the=
+maximal number of courses that can be taken.**
+{{:pasted:20200828-204101.png?500}}
+The technique here is a two stage process. First we sort by end dates. That lets
+us start trying to fit courses. We keep track of time and start at 0.
+Then we try the next course. If you can take it, great, take it! If you can't
+take it, we try something special.
+What we do is see if we can replace it with a course that we already took,
+that is longer. If we can do that, then great, take that one instead AND shift
+back our time by the time that we saved. SO the only thing we end up needing is
+a multiset of durations of courses we've taken.  Then at the end we just return
+the size of the set!
+Algrithm:
+<code>
+make a multiset of numbers
+sort by end date
+start a last_end int to 0
+iterate i from 0 to end of courses
+  if we can take the class : if last_end + courses[i][0] <= courses[i][1]
+    take it: last_end += courses[i][0], set insert courses[i][0]
+  if we CAN't take the class
+    is the largest element in the taken set longer or EQUAL to this course we can't take?
+      delete the largest elemetn in the set, and insert this new one.
+      last_end doesnt' stay the same! It gets shifted back by our time saved
+return size of set
+</code>
 Code No Memo: