0
$\begingroup$

How do we solve the weighted interval scheduling problem if given a maximum weight? I understand the solution for the problem when we are simply interested in the maximum weight possible, but how do we solve it when we need to find the maximum weight that cannot exceed a given weight?

Formally:

Given n tasks with start and finish times s and f, and weights w, return the tasks that result in maximum weight that does not exceed a given constant G. You can assume s,f,w and G are all positive integers.

$\endgroup$
  • $\begingroup$ The modifications to deal with the maximum allowable weight should be exactly the same as dealing with the maximum allowable weight in knapsack. $\endgroup$ – David Richerby May 9 '15 at 9:49
  • $\begingroup$ I know, trying to optimize better than knapsack :(, or at least to figure out ways to make it faster if we really care about each second of code spent in coding the algorithm $\endgroup$ – Danny Flint May 11 '15 at 7:55

Your Answer

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

Browse other questions tagged or ask your own question.