Picking a Group of Tasks while Minimising Time

The Problem

We are given N number of tasks of N days each. Each takes time t_i to performed. Our job is to find out which combination of tasks minimizes the total amount of time taken. The constraint is that one task has to be performed every 3 days.

Sample Inputs/Outputs

Input 1
3 2 1 1 2 3 1 3 2 1
Output 1

Here the correct solution is t_3, t_4, t_7, t_10

Input 2
1 2 3 3 1 2 5 6 1
Output 2

Here the correct solution is t_3, t_6, t_9

My Thoughts

I believe this can be solved using dynamic programming or a modification of the Continuous Knapsack Problem. But I don’t know how.

I thought of creating a graph starting with the first three tasks and having the next possible tasks as their children. Then to use the shortest path algorithm with weighted vertexes instead of weighted edges. But with values of N above even 1000, the memory limit of 32 MB will be easily exceeded.

I’m kind of thinking that there should be a mathematically creative solution to this?


What is the most efficient solution to this problem with the following limits?

1 ≤ N ≤ 2×10^5

The number of minutes of SUPW each day is between 0 and 10^4, inclusive.


The “a task has to be performed every 3 days” is ambiguous. Does it refer to the breaks between tasks being at most 2 days long, or the start/completion of some task in every 3-day interval, or? Please clarify.

Also, can a task be finished after those N days pass, or does it have to both start and finish during that N-day interval?

Yeah, it means that the breaks between two tasks can be 2 days long at most.

And the task for day i can be performed only on day i. But it is not necessary to perform every task due to the breaks.

It is knapsack in a certain sense, but it’s not NP-complete, because the upper bound on time is small :smiley:

One solution: DP, what is the min. time A[i] spent so far, if the last task so far was completed on day i? The next task to be performed is one of the tasks starting on days i+1,i+2 or i+3, which gives just 3 ways to move to larger states from state i. So all you need to do is iterate A[i+k-1+a[i+k]] =max(A[i+k-1+a[i+k]],A[i]+a[i+k]) for all i and 0 < k <= 3.

In case the tasks must end during the N-day interval, the answer is min(A[N],A[N-1],A[N-2]) because the last task had to end on one of these days. If we allow them to end later, try all possible days i when the last task overall starts; it can only be last if i+a[i]-1 >= N-2, and the answer is then iterated as min(answer,A[i-1],A[i-2],A[i-3]). You can start by adding a “dummy task” which ended at time 0, and so A[0]=0.

Time is O(N) because there’s just O(1) time per one of N states of DP.