I'm trying to pack sets of intervals, to find distinct buckets of intervals. The buckets should not be overlapping.

For example if I have these intervals:

A: [ [0, 10] ]
B: [ [1, 3], [5, 7] ]
C: [ [8, 10] ]

I want to get the following result:

[0, 1]: [A]
[1, 3]: [A, B]
[3, 5]: [A]
[5, 7]: [A, B]
[7, 8]: [A]
[8, 10]: [A, C]

What's the name of this problem?

  • $\begingroup$ I remember seeing something similar in 2D, in a computational geometry course. Maybe something from there could be connected to this problem. $\endgroup$
    – nir shahar
    May 10 at 14:27
  • 1
    $\begingroup$ Most problems one can come up with don't have a "name". Rather than asking for the name, it's usually better to figure out what you want to know about the problem (if you had the name, what problem would that enable you to solve?), and then ask about that. Then you have two ways to win: either someone suggests it is a standard problem and gives you a reference for how to solve it (e.g., gives you its "name"), or someone shows you a solution even if it doesn't have a standardly-accepted "name". $\endgroup$
    – D.W.
    May 10 at 18:05
  • 1
    $\begingroup$ What does it mean to "pack sets of intervals" or by "distinct buckets of intervals"? I don't understand the problem statement. Can you state the problem more precisely? I suggest listing the inputs to the problem, and the desired outputs. An example is not a substitute for a general specification -- please don't force us to guess or reverse-engineer what you have in mind based on an example. $\endgroup$
    – D.W.
    May 10 at 18:06
  • $\begingroup$ This might be a related problem. $\endgroup$ May 10 at 22:01

The problem can be stated as finding the elementary intervals for a given set of intervals. It is a technique frequently used for problems in computational geometry (as suggested by nir shahar also).


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.