# What will be an O(n) solution for this?

Suppose a given piece of work can be done at two processors. One at r and another at v. The job can run only at one processor at a time.

r = R1, R2 ... Ri, ...Rn

v = V1, V2,... Vi, ...Vn


There is a time penalty to switch between r and v, which is a constant say k. But I will have to maximize the total work done within x hours.

Xi represents the amount of work done in the ith minute.

I was thinking that comparing the Vi and Ri every minute and then if one is greater than the other by k make a switch. But that won't be optimal.

How can this be approached?

• Welcome to Computer Science! Can you add a url or reference to credit the original source? – Apass.Jack Dec 4 at 21:39
• @Apass.Jack Unfortunately I don't have either. – Pritam Banerjee Dec 4 at 21:41
• If you do not have either, how do you discover or know this problem? Please provide some background. – Apass.Jack Dec 4 at 21:44
• @Apass.Jack Total time is limited. How can you do all? – Pritam Banerjee Dec 4 at 23:08
• It seems similar to assembly line scheduling DP problem. You can take a look at that problem if it helps. – Navjot Waraich Dec 5 at 10:09