class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # time O(NlgN) space O(1)
        # step1: edge case no intervals
        if not intervals:
            return intervals
        # step2: sort in order of end , initialize end and res  
        intervals.sort(key = lambda k: k[0])
        res = []
        for ele in intervals:
            if not res or res[-1][1] < ele[0]:
                res.append(ele)
            else:
                # update end of last item in res
                res[-1][1] = max(res[-1][1],ele[1])
        return res 
        

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        graph = self.build_graph(intervals)
        nodes_in_comp, comp_number =  self.get_components(graph, intervals)
        return [self.merge_nodes(nodes_in_comp[comp]) for comp in range(comp_number)]
        # time O(E+V)= O(N^2)  space O(N^2)
    # generate undirected graph 
    def build_graph(self,intervals):
        graph = collections.defaultdict(list)
        for idx, interval in enumerate(intervals):
            for j in range(idx+1, len(intervals)):
                if self.overlap(interval,intervals[j]):
                    graph[tuple(interval)].append(intervals[j])
                    graph[tuple(intervals[j])].append(interval)     
        return graph
    
    def overlap(self,a,b):
        return a[0]<= b[1] and b[0] <= a[1]
    
    # merge all nodes in connected component into one interval
    def merge_nodes(self, nodes):
        start = min(node[0] for node in nodes)
        end =   max(node[1] for node in nodes)
        return [start,end]
    # get the connected componets of interval overlap graph
    
    def get_components(self, graph, intervals):
        visited = set()
        comp_number = 0
        nodes_in_comp = collections.defaultdict(list)
        
        def mark_component_dfs(start):
            stack = [start]
            while stack:
                node = tuple(stack.pop())
                if node not in visited:
                    visited.add(node)
                    nodes_in_comp[comp_number].append(node)
                    stack.extend(graph[node])
                    
        #mark all nodes in same connected components with same integer
        for interval in intervals:
            if tuple(interval) not in visited:
                mark_component_dfs(interval)
                comp_number += 1
                
        return nodes_in_comp, comp_number