Given a number of intervals:
-- (1, 3) a - (2, 3) b -- (2, 4) c -- (3, 5) d
intervals = [(1, 3), (2, 3), (2, 4), (3, 5)]
I would like to generate the minimum number of groups so that in each group any 2 intervals overlap.
[a, b, c] [c, d]
Please note that (1, 3) and (3, 5) are not considered overlapping intervals, so it is similar but not quite a duplicate of https://stackoverflow.com/questions/4962015/given-a-set-of-intervals-find-the-minimum-number-of-points-that-need-to-be-plac
Is there any efficient or not so efficient way to do this?
I guess I could just generate a set of overlapping intervals for each interval and then delete duplicated sets.
Edit: also not quite the same as calculating components from a graph, as an interval can be in more than 1 group