I have a problem similar to the interval scheduling algorithm. The differences are:
- The jobs have the same length.
- There are several categories of jobs and only one job from each category can be chosen.
- There can be no overlap in time between different categories.
I have illustrated the problem with a picture:
Each line is a job. Different color means that they belong to a different category. So I need to choose one of each colored line to try to cover as large an area as possible without any lines overlapping. Remember that lines with the same color should not be chosen twice. And yes, for the illustration the problem is trivial.
Does my problem have a name? Does it require a DP algorithm?