Convert a list of intervals into a list of disjoint intervals

Paul Royik

unread,

Jan 14, 2025, 9:45:06 PMJan 14

to sympy

I have a list of closed intervals sorted in ascending order by the left bound.

For example, [Interval(1,2), Interval(1,5)]. There is no sorting by right bouns, so [Interval(1,5), Interval(1,2)] is also possible.

I want to get list of disjoint closed intervals. For example, [Interval(1,2), Interval(1,5), Interval(2,3)] should become [Interval(1,2), Interval(2,3), Interval(3,5)] (again sorted by the left bound).

What is the best way to do it? Will the problem become harder if the list is unsorted?

Thank you.

Sangyub Lee

unread,

Jan 18, 2025, 2:36:50 PMJan 18

to sympy

For the first question, to sort the intervals according to right bounds, you can use python sort function with custom key function.

intervals = [Interval(1,5), Interval(1,2)]
sorted(intervals, key=lambda interval: (interval.left, interval.right))

The idea of the function is that Python compares tuples according to lexicographical order

(1, 2) < (1, 3)
(1, 2) < (2, 1)

so simply embedding into a tuple is equivalent to the logic to sort according to the left side, and then sort according to the right side.

I can answer the second question by time to time, because providing working code is more involved. But the general idea is that

Identify the list of endpoints of the intervals. For example, you can put into a list or a set. Set could be a good idea if you want to remove syntactic duplicates. From [Interval(1,2), Interval(1,5), Interval(2,3)]
From the sorted list of endpoints ([1, 2, 3, 5]), you can break down into a list of intervals. The desired result should be [1, 2], [2, 3], [3, 5]. You can use Python zip function with list slicing to break down the list like that, example, zip(l[:-1], l[1:]).
Compute the union of intervals. You can use Python | operator to compute the unions of sets. From the given list of intervals [Interval(1,2), Interval(1,5), Interval(2,3)], the union should be Interval(1, 5).
From the intervals that were computed from step 2: Interval(1, 2), Interval(2, 3), Interval(3, 5). You should check if each broken down intervals are subset of the union computed from step 3. In this simple example, every broken down intervals are already contained in the union. You can use the function issubset.

I note that the question is a bit ambiguous, and if you take account of more complexity, like open-closedness of intervals, or symbolic numbers which can make comparison difficult, the solution can be different. But I expect that the general answer should be similar.

Paul Royik

unread,

Jan 18, 2025, 3:40:35 PMJan 18

to sympy

Thank you very much!

Chris Smith

unread,

Apr 8, 2025, 6:17:20 PMApr 8

to sympy

Union already knows how to do this:

>>> Union(Interval(1,5), Interval(1,2),Interval(2,3),Interval(7,10))
Union(Interval(1, 5), Interval(7, 10))

/c

Reply all

Reply to author

Forward