Let's say that I have one task to perform $n$, $n<250000$ times and it takes $p$, $p < 700000$ time to complete it once.

I have list of time constraints ${t_1, t_2, ..., t_n}$ where $t_1\le t_2\le \cdots\le t_n\le 10^9$. This list says that the $i$-th execution of task cannot be ended earlier than $t_i$.

I want to minimize following sum: $\sum_{i=1}^{n} (e_i-t_i)$ where $e_i$ tells me when the $i$-th execution of task has ended. So I want to minimize a sum of wait-times for each task execution. Example:

$n = 4$; $p=3$; $t=\{1,2,7,15\}$; Answer: 8

Explanation: We start doing first task at time 0 and we end at time 3 (wait-time so far is 2). We start doing second task at time 3 and end at time 6 (total wait-time is 6). We start doing third task at time 6 and end at time 9 (total wait-time is 8). We start doing last task at time 12 and end at time 15 (total wait-time is still 8).

I can easily calculate this sum in $O(n)$ because it's equivalent to: $$\sum_{i=2}^{n} \max(0, e_{i-1}+p-t_i) + \max(0,p-t_1)$$ $$e_i=\max(t_i, e_{i-1} + p)$$ $$e_1=\max(t_1, p)$$ but let's say that I have $k$, $k<300000$ tasks, each task has it's own running time $p_j$ and I want for each task with running time $p_j$ calculate minimize above sum (time constraints remains the same for each $p_j$).

A naive approach would give me running time $O(nk)$. Is there a better way?

  • 1
    $\begingroup$ What's the context where you encountered this question? Can you credit the source in the question? What approaches have you tried? Have you tried all reasonable greedy strategies? Have you tried dynamic programming? $\endgroup$ – D.W. Nov 22 '17 at 1:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.