naved momin wrote:
The thing which I want to understand is out of 5 Intervals why only those 3 Intervals (mentioned above) is selected ?
Ryan McGuire wrote:
the top line shows the maximum worker usage A + D + E = 150 + 150 + 90 = 390.
Matthew Brown wrote:
I think I can see a way of solving the general case, though it isn't simple and I'm not certain there isn't a better way. Half the battle in some of these problems is working out the right way to represent the problem. My idea is to represent the problem as a weighted directed graph:
- Each task is a node, and we also add Start and End nodes.
- We add an edge from the Start to every task node, and from every task node to the end node
- We also add an edge from every node to every other node that can follow it
- The weights of each edge are the duration of the task that the edge points towards (and zero for the End edges).
So now any path through the graph from Start to End is a valid selection of tasks, and the sum of the edge weightings on that path is the total work time. So the problem is to maximise this sum. So it's a Longest Path problem. That isn't straightforward, but it is a standard graph problem* with some established algorithms, if you're familiar with those.
(* Well, Shortest Path is a standard graph algorithm, but if you negate all the weightings it's equivalent, as long as you're using an algorithm that can cope with negative weights).