0
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ How long does a task takes to be completed? $\endgroup$ – xskxzr Sep 26 '20 at 0:23
  • $\begingroup$ 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 $\endgroup$ – Area Sep 26 '20 at 1:52
  • $\begingroup$ might have phrased it wrong please re-visit/phrase [start time, end time], both of which are on top of hours. What is D? $\endgroup$ – greybeard Sep 26 '20 at 6:46
  • $\begingroup$ With start time, end time specified, is the problem indeed to pick tasks? $\endgroup$ – greybeard Sep 26 '20 at 6:53
0
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – Area Sep 26 '20 at 1:50
  • $\begingroup$ 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? $\endgroup$ – timg Sep 26 '20 at 4:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.