title: Find minimum time to perform job using two machines
body: <p>I was going through some questions and I found a question <a href="http://learn.hackerearth.com/question/360/n-2-problem/" rel="nofollow">here</a>. It requires a dynamic programming algorithm. I tried to come up with a recurrence but I don't think it will always give the correct result. If we don't take into account the limit K then, its easy to have a recurrence which finds minimum time, <strong>which I think can be done using greedy approach as well</strong>, please correct me if I am wrong. But for the limit K we need to take into account that in the later stage we might think of using a value i of machine A but it might have completed K limit. So this needs to be backtracked. I think we might need to keep one more dimension for taking this into account. But I am unable to think of how to encompass that situation, using an extra dimension. Please provide some help.</p>
  
  <blockquote>
    <p>You are given 2 machines. There are N jobs you have to perform. Job i takes Ai time to perform on machine A and Bi time to perform on machine B. Each job should be done either on machine A or B. The jobs should be performed in order. Given the arrays A and B and an integer K, find the minimum time required to complete the jobs, given that you cannot do more than K jobs on the same machine continuously. This can be done in O(N K)space and time. This can be improved to O(N K) time and O(N ) space and further to O(N logN ) time. </p>
  </blockquote>