Skip to main content
4 of 4
Fixed spelling and grammar of title
MTS
  • 8.6k
  • 2
  • 35
  • 65

How to get the largest subset of a set of sets of intervals with no overlapping intervals

Given: Set of Set of Intervals. Example {{(1,2), (3,4)}, {(1, 3)}, {(13,14)}}

Wanted Result: Largest Subset, in which no Interval overlaps with another from every Set pairwise.

Example:

Input {{(1,2), (3,4)}, {(1, 3)}, {(13,14)}}

A possible Solution would be: {{(1,2), (3,4)}, {(13,14)}}

Another could be {{(1, 3)}, {(13,14)}},
it's not important that the solution above has more 'subelements',
its only important that 2 = |{{(1,2), (3,4)}, {(13,14)}}| = |{{(1, 3)}, {(13,14)}}|

Now i am looking for a good/efficient Algorithm to solve that problem.