I Want To Input A List Of Intervals And Check The Intervals Of The Union Of Overlapping Intervals And The Intervals Of Non-overlapping Intervals

For example: I have the intervals = [[-5,-3],[-4,-1],[1,3],[4,8],[5,10],[10,12], [15,20]] (not necessaraly sorted like that) I want the function to return me [[-5,-1],[1,3],[4,12],

Solution 1:

So what I understand is that you would like to find intervals which are connected or overlapped, you may do that by using an iterator.

defmaxDisjointIntervals(intervals):  # dont use list_ as your variable name
    overlappedIntervals = []

    iflen(intervals) == 0:
        return overlappedIntervals

    # sort the intervals using the starting time
    intervals = sorted(intervals, key=lambda interval: interval[0])

    # init the start hour and end hour
    startHour = intervals[0][0]
    endHour = intervals[0][1]

    for interval in intervals[1:]:
        # if there is an overlapif interval[0] <= endHour <= interval[1]:
            endHour = interval[1]
        # if there is not an overlapelse:
            overlappedIntervals.append([startHour, endHour])
            startHour = interval[0]
            endHour = interval[1]
    overlappedIntervals.append([startHour, endHour])
    return overlappedIntervals


print(maxDisjointIntervals([[-5, -3], [-4, -1], [1, 3], [4, 8], [5, 10], [10, 12], [13, 20]]))

output: [[-5, -1], [1, 3], [4, 12], [13, 20]]

Solution 2:

You can use reduce from functools to merge the intervals together:

intervals = [[-5,-3],[-4,-1],[1,3],[4,8],[5,10],[10,12], [15,20]]

from functools import reduce
disjoints = [*reduce(lambda a,b: a+[b] ifnot a or b[0]>a[-1][1] else a[:-1]+[[a[-1][0],b[1]]],intervals,[])]

print(disjoints) # [[-5, -1], [1, 3], [4, 12], [15, 20]]

or do the same thing in a basic loop:

disjoints = intervals[:1]
for s,e in intervals[1:]:
    if s>disjoints[-1][-1]: disjoints.append([s,e])
    else: disjoints[-1][-1] = e
    
print(disjoints) # [[-5, -1], [1, 3], [4, 12], [15, 20]]

note: this assumes inclusive ranges. If the end is exclusive use >= instead of >.