# Optimal Selection of Non-Overlapping Jobs

I'm trying to find what the family of problem is - as well as an approach - for the following:

I have a set of tasks T = [t1, ..., tn] to do, each of which has a corresponding reward ri. Each task takes place during a fixed interval - ie: task 1 is from times 1-4, task 2 from 2-5, and task 3 from 9-15. This means that I would have to pick either task 1 or 2 depending on which is more valuable, and then task 3 which does not conflict with either of the previous.

I'd like for this to scale to n tasks, and also to m "CPU's" - where more than one task can be executed in parallel. This reminds me of the knapsack problem, but maybe an interval graph would provide a better approach?

Any suggestions on how to approach this problem, or any relevant references?

• To show the OP's problem is NP-hard, the reduction needs to go in the opposite direction. Weighted MIS cannot be directly reduced to this problem, because certain combinations of edges are impossible to represent as overlaps in an interval graph: E.g. if $a$ and $b$ both overlap $c$ and $d$, and $c$ and $d$ do not overlap each other, then $a$ must overlap $b$. – j_random_hacker Apr 3 at 7:34