Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.


"""
<1> sort by first element in each interval say as x[0]
<2> if result list is empty or previous interval end < next interval start,
append current interval to the result list
else which means they ovelapped each other, we will select the max(previous.end,next.end)
then update the previous end with max value
"""


class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x:x[0])
        merge_res=[]
        for interval in intervals:
            if len(merge_res)==0 or merge_res[-1][1]<interval[0]:
                merge_res.append(interval)
            else:
                merge_res[-1][1]=max(merge_res[-1][1],interval[1])
        return merge_res
        
