# 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? Sep 26, 2020 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, 2020 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? Sep 26, 2020 at 6:46
• With start time, end time specified, is the problem indeed to pick tasks? Sep 26, 2020 at 6:53

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 "x" 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

• Hello! Thanks for the response. I'm still slightly confused as to what each of i and j represent in the dp(i,j,k)...Also the question statement was that there are two machines, a and b, and a smaller task that requires one machine can use either a or b, while a larger task that requires two machine need both a and b at the same time. Sorry about any misunderstanding.
– Area
Sep 26, 2020 at 1:50
• If we visualize time as x coordinates on a number plane, i would be the position of machine 1 j would be the position of machine 2 Also, are you given in the input which tasks need both machines, or is there a certain threshold which decides wether a task needs both machines?
– timg
Sep 26, 2020 at 4:58