# 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.

• How long does a task takes to be completed? – xskxzr Sep 26 '20 at 0:23
• I might have phrased it wrong, but the tasks are basically given as [[task 1 start time, task 1 end time, need both machine], [task 2 start, task 2 end, need only one], [task 3 start, task 3 end, need one machine] ... ], and there are n such entries in total representing tasks that need to be scheduled – Area Sep 26 '20 at 1:52
• might have phrased it wrong please re-visit/phrase [start time, end time], both of which are on top of hours. What is D? – greybeard Sep 26 '20 at 6:46
• With start time, end time specified, is the problem indeed to pick tasks? – greybeard Sep 26 '20 at 6:53