How to do interval union of numbers, like you do in math

Question

How to do interval union, like you do in math. For example, the ranges 1 to 3 and 2 to 4, when joined, result in the range 1 to 4 because parts of them coincide.

So input: [1, 3] [2, 4]

would have output: [1, 4].

But input: [1, 3] [4, 5]

output:

[1, 3] [4, 5]

would produce [1, 3] [4, 5] because no part of the intervals match. The function must be able to join the various ranges that are given in the string (which may not be in order)

for example:

Input:

[1, 3] [3, 4] [5, 8] [6, 10]

Output:

[1, 4] [5, 10]

What did you search for, and what did you find? What did you try, and how did it fail? — tripleee, Mar 21 '22 at 11:28
is this a problem from a challenge? If we do it for you it defeats the purpose of the problem. — , Mar 21 '22 at 11:31
Agreeing with former comments. Think of intersections, you could produce an algorithm for that. — null, Mar 21 '22 at 11:33
Does this answer your question? [Merging Overlapping Intervals in Python](https://stackoverflow.com/questions/49071081/merging-overlapping-intervals-in-python) — Guybrush, Mar 23 '22 at 09:51

Sash Sinha · Accepted Answer · 2022-03-21T11:47:39.750

Maybe you could sort the intervals by their start values and then subsequently check if each interval should be merged or not:

from typing import NamedTuple
from prettytable import PrettyTable

def merged_intervals(intervals: list[list[int]]) -> list[list[int]]:
    if not intervals:
        return []
    sorted_intervals = sorted(intervals, key=lambda i: i[0])
    merged = [sorted_intervals[0]]
    for start, end in sorted_intervals[1:]:
        if merged[-1][1] >= start:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

class TestCase(NamedTuple):
    intervals: list[list[int]]
    expected: list[list[int]]

def main() -> None:
    t = PrettyTable(['intervals', 'expected', 'actual'])
    t.align = 'l'
    for intervals, expected in [TestCase([[1, 3], [2, 4]], [[1, 4]]),
                                TestCase([[1, 3], [4, 5]], [[1, 3], [4, 5]]),
                                TestCase([[1, 3], [3, 4], [5, 8], [6, 10]],
                                         [[1, 4], [5, 10]])]:
        t.add_row([intervals, expected, merged_intervals(intervals)])
    print(t)

if __name__ == '__main__':
    main()

Output:

+-----------------------------------+-------------------+-------------------+
| intervals                         | expected          | actual            |
+-----------------------------------+-------------------+-------------------+
| [[1, 4], [2, 4]]                  | [[1, 4]]          | [[1, 4]]          |
| [[1, 3], [4, 5]]                  | [[1, 3], [4, 5]]  | [[1, 3], [4, 5]]  |
| [[1, 4], [3, 4], [5, 8], [6, 10]] | [[1, 4], [5, 10]] | [[1, 4], [5, 10]] |
+-----------------------------------+-------------------+-------------------+

How to do interval union of numbers, like you do in math

1 Answers1