dynamic programming – 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.