Обсуждение @ 1403. Курьер @ Timus Online Judge

How to solve this problem in O(n^2)

Послано Anton [SUrSU] 13 авг 2006 01:21

Give me some hints please

Re: How to solve this problem in O(n^2)

Послано azadeh 13 авг 2006 01:32

you can use dynamic programming

Re: How to solve this problem in O(n^2)

Послано Anton [SUrSU] 14 авг 2006 00:46

Please, tell me how to dp?

You can solve this program in O(n*log n),

Послано TheBeet 18 авг 2006 19:22

I just use a heap.

Edited by author 18.08.2006 19:22

Hint

Послано ASK 10 мар 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

Обсуждение задачи 1403. Курьер