Given a list of intervals, perform the union of them, and reduce overlaps.
That means, overlapping parts are reduced. ([a, b] U [c, d] = [a, d]
if b > c
)
Assuming all a < b in all intervals [a, b]
.
Implement as a function of a list of input intervals -> list of output intervals.
Shortest code wins. You cannot use any existing libraries.
Clarifications:
- Open and closed intervals are not distinguished.
- Intervals for real numbers, not integers. (
[2, 3], [4, 5] -> [2, 3], [4, 5]
) - No need to sort output intervals
- The order if inputs do not matter
- Illegal inputs are only
[a, b]
whereb >= a
, it has nothing to do with the order of input intervals and the number of input intervals. - You do not need to show an error message on undefined behaviors
Examples (with number lines)
[2, 4], [7, 9] --> [2, 4], [7, 9]
234
789
-> 234 789
[1, 5], [2, 10] --> [1, 10] (overlapping [2, 5] reduced)
12345
234567890
-> 1234567890
[2, 4], [3, 6], [8, 9] -> [2, 6], [8, 9]
234
3456
89
-> 23456 89
[4, 2], [2, 2] -> (undefined behavior: against the assumption)