The article is written in
CoffeeScript

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | # The goal is to maximize the active time. # **Insight:** let p(n) be the nearest task before n that doesn't overlap it, # * Task n either belong in the optimal solution or doesn't. # * If task n belongs to the optimal solution, then tasks {1...p(n)} also belong; # or else, we could have replaced that range with a better one, without # overlapping n. # * If n didn't belong, the optimal active time is equal to the one consisting of # {1...n - 1} # Basically, optimal(n) = max(n's duration + optimal(p(n)), optimal(n - 1)) recursivelySchedule = (taskNo, tasks, memoizer = {}) -> if taskNo is 0 then 0 else if memoizer[taskNo]? then memoizer[taskNo] else memoizer[taskNo] = Math.max tasks[taskNo].duration + recursivelySchedule(tasks[taskNo].previousNonOverlappingTask, tasks, memoizer), recursivelySchedule taskNo - 1, tasks, memoizer iterativelySchedule = (taskNo, tasks) -> tracker = [0] for i in [1..taskNo] tracker[i] = Math.max tasks[i].duration + tracker[tasks[i].previousNonOverlappingTask], tracker[i - 1] return tracker[tracker.length - 1] module.exports = recursivelySchedule: recursivelySchedule iterativelySchedule: iterativelySchedule |

Category: coffee

*This article was last modified: Sept. 23, 2017, 6:54 p.m.*

wikicoding is a free and open source project under the GPLv3 license.You can find the source code and contribute to the project via github - wikicoding

Every code has a silver lining.