Interval best time picking

Правка en3, от Bunik, 2022-11-01 21:22:30

Given a set of intervals in format [startTime, endTime, period], indicating that a task need to be completed between startTime to endTime and period indicates amount of time required to complete the task.
A task can be completed in discontinuous time.
Multiple tasks can be done at same time. Find the minimum time required to complete all tasks.


Example:
[1,5,2]
[2,5,2]
[1,3,2]
[6,6,1]
[5,9,3]
[8,9,2]


Minimum time will be 5 as we can pick [2,3] by which all first 3 taks will be done and then, pick [6] for completing 4th task and 1 unit of 5th task. Now, pick [8,9] for remaining work of 5th task and to complete last task.


Constraints:
Number of Tasks<=1e3
Interval Times<=1e6


This is a question from online assessment of some company, which is completed now. Could not get any idea other than greedy which didn't work.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский Bunik 2022-11-01 21:22:30 9 Tiny change: 'nInterval Length<=1e6<br>\' -> 'nInterval Times<=1e6<br>\'
en2 Английский Bunik 2022-11-01 21:21:32 90 Tiny change: ':\n[1,5,2]\n[2,5,2]\' -> ':\n[1,5,2]<br>\n[2,5,2]\'
en1 Английский Bunik 2022-11-01 21:19:47 890 Initial revision (published)