# coloring of an interval graph with constraints

Given an interval graph that represents a set of tasks, in a given period of time, to be assigned to a set of employees, the objective is to find a minimum coloring of this graph such that the total duration of the tasks corresponding to each color does not exceed a constant $$W$$ and there exists, for each color, at least to successive activities where the elapsed time between them is greater than or equal a constant $$R$$

I don't know how to solve this problem or how to transform it to a know problem.

• This is NP-hard by reduction from Knapsack ("each color does not exceed a constant $W$" is the key element), even ignoring the requirement for a "break" of length $R$. That means nobody knows a way to solve it efficiently, unfortunately. – j_random_hacker Oct 13 at 12:18
• In fact, the constant $W$ is fixed it is equal to 10 and the $R$ also. Do you think that the problem remains NP-hard? – Farah Mind Oct 13 at 22:52