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


Create a graph as follows:

  • each vertex is one of the intervals

  • two vertices are connected by an edge if their intervals overlap.

Now the problem you stated is equivalent to finding all cliques in an undirected graph, which is a pretty tough problem, since it is NP-hard. You may be able to find some pointers to algorithms which give you a suboptimal solution, but don't expect too much.

  • Seems like the correct approach! I will study if it is worth to implement this or just delete duplicated sets. Thank you very much!
    – Stradivari
    Aug 27 '19 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.