We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Solved with a simple sorted list of deadlines. First key was to realize all tasks have to be completed in order of deadline, there is no better way to do it to minimize the time a deadline has been missed.
I failed tests 5-9 due to timeout until I realized that when I have a task that goes over by the maximum amount of any task in my list, I don't care about any tasks with deadlines before that ever. In the example:
2 2
# task 1 is not late, 0
1 1
# task 2 is earlier so it goes first and is on time,
# task 1 is not late by 1 (the max), so I no longer
# care about task 2
4 3
# task 2 is late by 1 (3 units of work done), task 3 here
# is now late by 2 (6 units of work done), so I no longer
# care about task 2
10 1
# task 3 is late by 1 still, at deadline 10 I have
# task 4 that has 7 units of work before it and isn't late
2 1
# since task 3's deadline is later, I just add the work
# to all the deadlines remaining, meaning
My Submission I think could fail under certain test cases so I think there must be a better way. The worst case would be 99,999 tasks in order with Di of index + 1 and Mi of 1. I think I could solve that though. Maybe there should be a tougher problem set like that? How did other people solve it?
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Task Scheduling
You are viewing a single comment's thread. Return to all comments →
Solved with a simple sorted list of deadlines. First key was to realize all tasks have to be completed in order of deadline, there is no better way to do it to minimize the time a deadline has been missed.
I failed tests 5-9 due to timeout until I realized that when I have a task that goes over by the maximum amount of any task in my list, I don't care about any tasks with deadlines before that ever. In the example:
My Submission I think could fail under certain test cases so I think there must be a better way. The worst case would be 99,999 tasks in order with Di of index + 1 and Mi of 1. I think I could solve that though. Maybe there should be a tougher problem set like that? How did other people solve it?