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.

enter image description here

Does my problem have a name? Does it require a DP algorithm?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.