Interval Scheduling problem with more than 1 machine There are 2 machines.
Each task either requires 1 or 2 machines to run (ie, a 1-machine task can run in parallel with another 1-machine task but a 2-machine task occupies both machine
The list of n tasks are given in [start time, end time], both of which are on top of hours. If we were to order the tasks by non decreasing end time the maximum would be D, but the list given is not sorted.
There is no value difference (1 machine and 2 machine tasks are considered same value). Just schedule as many tasks as possible. Want to find an algorithm that runs within O(nD^2) time
I'm considering DP but can't really get my head clear on how to approach the question. Any suggestion would be helpful.
You may want to consider a solution with dp(i, j, k) where i represents the x that machine 1 is at, j represents the x that machine 2 is one, and k represents the index of the task you're considering
The state transition in this case would be O(1) because you either take the task or not, for which you can increment/decrement i/j accordingly.
I'm not sure what D and n are but if D refers to the amount of time allotted for machine 1 and 2 and n is the number of tasks, then I believe this could be the solution you're looking for
Note that &quot;x&quot; refers to time. Also, this solution would work if the tasks were assigned a value
Let me know if you want an implementation of this