Bunik's blog

Interval best time picking
By Bunik, history, 18 months ago, In English

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.

  • Vote: I like it
  • -1
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
18 months ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

I think greedy works. Sort tasks by start time. Sweep over the time units. At each point we have a choice — Take this time unit or wait and take a later one. If we can take a later time and still complete the task with the smallest difference (time left in interval — time units still needed), it's better to choose the later time. Reason is that choosing the later time still guarantees that we complete that task, but going to a later time might mean that we step over a new interval start and share the chosen unit with more tasks. We can never share with less tasks by taking a later time because if some task completes before this one we are guaranteed to share all their remaining time units.

"But wait, that takes 1e3*1e6=1e9 and is too slow!?" Not if we go by intervals — There are only 3*1e3 interesting times total. Just step to each of them and do math to see if/how many units we need to choose on each interval. Also consider keeping active intervals in a heap by (time remaining — time still required).

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This problem is not easy. It requires a pretty good skill on greedy+implementation+handling edge cases skill. No need to feel bad!

    I often find these kinds of greedy problems difficult like the ones on the interval based or scheduling-based. Getting a correct greedy idea is difficult. Any suggestions on how to get good at these kind of problems or in general related greedy problems. "Just solve more greedy problems is the suggestion?"

    I like your idea, i will get back to you after implementing your idea. Please help me if i do wrong, thanks!

    → Reply
    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      This problem is not easy

      Scheduling problems can indeed get as hard as any problem can, like that one problem on ICPC WF 2017

      → Reply