56. Merge Intervals.md

56. Merge Intervals (Medium)

• sort all array by start. [[1,3],[2,6],[8,10],[15,18]]
• append it to ans list first, if new list can be merged, change ans list. If not, append to ans list.

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x:x[0])
        ans = []
        for interval in intervals:
            if not ans or ans[-1][1] < interval[0]:
                ans.append(interval)
            else:
                # case of [[1,4],[2,3]]
                ans[-1][1] = max(interval[1], ans[-1][1])
        
        return ans