1

Interval best time picking

 1 year ago
source link: http://codeforces.com/blog/entry/108625
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client
By Bunik, history, 24 hours 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.

15 hours ago, # |

← Rev. 2 →  

+1

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).

  • 83 minutes ago, # ^ |

    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!

    • 54 minutes ago, # ^ |

      This problem is not easy

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

      • 48 minutes ago, # ^ |

        Thanks for a resource! Solving more problems is the only way to improve? I found this problem really difficult, may be i haven't solved many problems on these(interval based). I find these greedy questions difficult unlike usual cf div2 rounds where greedy usually be based on binary search or two pointer or sorting and some observation.

  • 50 minutes ago, # ^ |

    Here is the implementation of your idea: https://pastebin.com/CvaDS6L5 I don't know if it is correct or not. I don't find any flaw. Could you please validate it for me?

    Thanks! I like your idea!

    Here is the main snippet from the above-mentioned code.

    Greedy Implementation

44 minutes ago, # |

Any online judge or platform where this problem is present? so that i can validate my solution https://pastebin.com/CvaDS6L5

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK