Interval best time picking

Revision en1, by Bunik, 2022-11-01 21:19:47

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 Length<=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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Bunik 2022-11-01 21:22:30 9 Tiny change: 'nInterval Length<=1e6<br>\' -> 'nInterval Times<=1e6<br>\'
en2 English 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 English Bunik 2022-11-01 21:19:47 890 Initial revision (published)