1

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

Improve this question
0

1 Answer 1

Reset to default
2

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.

Improve this answer
1
  • Seems like the correct approach! I will study if it is worth to implement this or just delete duplicated sets. Thank you very much! Commented Aug 27, 2019 at 15:13

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.