LC56 Merge Intervals

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        """  tc O(NlgN)  sc O(1)
        main idea: find overlapping pair  ==>  previous end is bigger than current start time 
        1. sort by start 
        2. for each time pair, check if overlap with stack top 
        3. if overlap, update stack top, otherwise push pair into stack 
        """
        st = []
        intervals.sort(key = lambda x: x[0])
        for s,e in intervals:
            if st and st[-1][1] >= s:
                st[-1] = [st[-1][0],max(st[-1][1],e)]
            else:
                st.append([s,e])
        return st