Minimum execution time [duplicate]

Question

This is a question asked in a coding platform. I couldn't find the answer anywhere.

There are 3 arrays which has execution time of programs. The programs need to be executed in sequential manner.(i+1th element of an array can not come after ith of the same array). Find the minimum execution time.(calculated as cumulative execution time of each programs).

For E.g:

program1 = [2,1]
program2 = [1]
program3 = [1]

One of the flow would be program2[0], program3[0], program1[0], program1[1] i.e [1,1,2,1] The execution time for the above is calculated as 1+(1+1)+(1+1+2) = 7 (considering, time required for the first element is zero)

I tried taking the smallest of each array each time, but it works only for some of the arrays. Like,

program1 = [23, 10, 18, 43]
program2 = [70, 1, 1, 1]
program3 = [13, 42]

In this example, program2 will be picked last, and that is not the optimal solution.

What would be the approach to solving this? Is there a similar problem I can look up?

Answer 1

Your explanation is not great, but what I understand from your example is that you have three arrays, each array represents a sequence of processes that need to be processed in the order of presence in the array (each value is the total time required to finish processing current process). You are looking for the minimum sum of waiting times of all process. Each process's waiting time is calculated as the sum of all processing time of all previously processed processes.

If you are looking for an optimal solution, you can use dynamic programming like this: let dp[i][j][k] be the total processing time required to process the first i elements from the first array, and first j from second and first k from third. You are looking for dp[n][m][p] where n is the total number of elements in the first, m in the second, k in the third.

our base cases are dp[1][0][0] and dp[0][1][0] and dp[0][0][1], where each represents taking the first element from each array, and the first element will wait zero times always.

Now dp[i][j][k] = min(dp[i-1][j][k]+sum1,dp[i][j-1][k]+sum2,dp[i][j][k-1]+sum3), where:

sum1 = sum first i-1 elements from first array, first j elements from second, first k from third.

sum2 = sum first i elements from first array, first j-1 elements from second, first k from third.

sum3 = sum first i elements from first array, first j elements from second, first k-1 from third.

You can calculate them in O(1) each time by preprocessing all prefix sums in O(n+m+p).

The total time complexity should be O(n.m.p) since you will visit each state only once and the total time required to compute the value of each state is O(1) using prefix sums as mentioned above.

If you are not looking for an optimal solution, you can try other heuristics like choosing the min current element, or choosing an element from the array with the current largest/smallest sum of remaining values, and many more ideas that you can try and that should run in O(n+m+p) time.