Discussion @ 1403. Courier @ Timus Online Judge

Show all messages Hide all messages

How to solve this problem in O(n^2) Anton juver++ Postnikov 13 Aug 2006 01:21

Give me some hints please

Re: How to solve this problem in O(n^2) azadeh 13 Aug 2006 01:32

you can use dynamic programming

Re: How to solve this problem in O(n^2) Anton juver++ Postnikov 14 Aug 2006 00:46

Please, tell me how to dp?

You can solve this program in O(n*log n), TheBeet 18 Aug 2006 19:22

I just use a heap.

Edited by author 18.08.2006 19:22

Hint ASK 10 Mar 2010 16:23

Sort by finish time. For every delivery do: if current delivery time is greater than the number of already scheduled deliveries, schedule it; else (that is, it is equal), replace the least important scheduled delivery with this one. Altogether O(n log(n)).

Edited by author 10.03.2010 18:40

Edited by author 10.03.2010 18:40

Discussion of Problem 1403. Courier