New answers tagged

0

It seems you consider intervals totally contained in others or disjoint only. Intervals can overlap partially, e.g. $[1, 3), [2, 4)$. Scheduling in the general case (any value function for tasks, where you look for the maximum sum of values) is hard (the corresponding decision problem is NP-complete). There is copious literature on algorithms to solve this, ...


1

I think you mean partial order, as if you only have a preorder then there might not even exist any total order that is compatible with it. Your argument seems to be missing something about how you construct your topological sort, as it implies that any topological sort works, which you disproved yourself. In your example $x,y,x',y'$ could be a topological ...


Top 50 recent answers are included