Merge Intervals

Given a list of intervals, how can we produce a resultant list of intervals that contains only non -overlapping intervals.

Take, for example, that we have [ [1,4], [4,5] ], here 4 is overlapping both intervals.
So the resultant will be [ [1,5] ].
Let us consider another example, [ [1,3],[2,6],[8,10],[15,18] ]. Here 2 exists between [1,3].
So the resultant list becomes [ [1,6], [8,10],[15,18] ].

And the problem does not specify that the input is sorted. We have to sort the input before merging.
First we sort the intervals by the first item – start of the interval.While iterating, we check if the new item exists between current interval, if it does, we expand the current interval. Otherwise, the first interval is added to the result list and new item becomes the current interval. Iterate until the list is complete.

Finally, the last item that remained will be added to result at the end.

def merge(intervals):
    intervals = sorted(intervals, key=lambda x: x[0])
    current_interval = intervals[0]
    result = []
    for index in range(1, len(intervals)):
        if current_interval[0]<=intervals[index][0]<=current_interval[1]:
            if intervals[index][1] >=current_interval[1]:
                current_interval = [current_interval[0], intervals[index][1]]
        else:
            result.append(current_interval)
            current_interval = intervals[index]
    result.append(current_interval)
    return result
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        return merge(intervals)