leetcode medium : Merge Intervals (Facebook 코딩 인터뷰 기출)

Merge Intervals

https://leetcode.com/problems/merge-intervals/solutions/?orderBy=most_votes

풀기 전

예전에 풀어본 문제라서 기억대로 풀었다.

인터벌 시작점을 기준으로 정렬하고 첫 인터벌을 정답리스트에 추가한다.

그 다음 인터벌을 볼 때 부터는 정답리스트의 마지막요소의 end랑 지금 보고 있는 인터벌의 start를 비교하면 merge할지 안할지 쉽게 결정할 수 있다.

코드 설명

class Solution:
    def merge(self, intervals):
        ans = []

        for interval in sorted(intervals):
            if not ans or ans[-1][1] < interval[0]:
                ans.append(interval)
            else:
                ans[-1][1] = max(ans[-1][1], interval[1])

        return ans

특별히 설명이 필요 없는 코드같다.

분석

O(N log N).

 

여기까지만 하면 facebook coding interview의 난이도라고 하기엔 민망하다.

솔루션 학습

또 다른 솔루션이 있다길래 공부할겸 읽어봤다. (Facebook 인터뷰의 Follow-up question이라고 한다.)

Question: How do you add intervals and merge them for a large stream of intervals? (Facebook Follow-up Question)

 

질문의 요지가 이해 안되는 분들을 위해 보충설명을 작성해보았다.

[보충설명]

아마 문제를 푸셨다면 sorting solution으로 풀었을겁니다.

딱 한 번만 merged intervals를 구하면 된다는 가정하에 가장 간단하니까요.

이젠 대량의 데이터가 스트림으로 들어오는 상황이라고 가정하겠습니다.

K개의 데이터가 들어올 때마다 merged interval을 구해야 하는 상황입니다.

K는 충분히 작은 수입니다. (아무리 커도 log N보다 크진 않습니다.)

K=1이라고 생각하고 데이터가 하나 들어올때마다 merged intervals를 얻어야 한다고 가정해도 됩니다.

자, 이런 상황에서 sorting solution보다 유리한 솔루션이 있을까요?

만약 그 솔루션을 생각하셨다면, K의 범위에 따라서 두 솔루션 중에 어떤 솔루션이 효율적일까요?

 

We need to have two functions for the tree (add interval and query tree).

Implementation Details

TreeNode - On top of the left child, right child, start boundary, and end boundary, we have a middle field that determines whether a new interval goes to the left child, right right or merged with the current node.

add - If the new interval touches or crosses the middle of the current node, we update the current node. Otherwise, we put the new interval into the left subtree or right subtree.

• Why do we use middle for comparison and not start or end boundaries?The reason is that we can use merge-sort technique to query the merged intervals result when the left subtree does not overlap with the right subtree.

query - Use merge-sort technique by retrieving the merged intervals of the left subtree (i.e. left_intervals) and those of the right subtree (i.e. right_intervals). Because of the implementation of add, we can guarantee that

• if there's an interval in the left_intervals that overlaps with the current node, then we know that all the intervals after that interval overlaps with the current node.
• The first few intervals or zero intervals in the right_intervals overlap with the current node.

class TreeNode:
    def __init__(self, start, end, middle):
        self.start = start
        self.end = end
        self.middle = middle
        self.left = self.right = None

class Solution:
    def __init__(self):
        self.root = None
    
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if not intervals:
            return []
        
        for start, end in intervals:
            if not self.root:
                self.root = TreeNode(start, end, (start + end) // 2)
            else:
                self.add(self.root, start, end)
        
        return self.query(self.root)
    
    
    def add(self, node, start, end):     
        if end < node.middle:
            if node.left:
                self.add(node.left, start, end)
            else:
                node.left = TreeNode(start, end, (start + end) // 2)
        
        elif start > node.middle:
            if node.right:
                self.add(node.right, start, end)
            else:
                node.right = TreeNode(start, end, (start + end) // 2)
        
        else:
            node.start = min(node.start, start)
            node.end = max(node.end, end)
    
    def query(self, node):
        if not node:
            return []
        
        # merge-sort divide and conquer
        left_intervals = self.query(node.left)
        right_intervals = self.query(node.right)
        res = []
        
        inserted = False
        
        for lres in left_intervals:
            if lres[1] < node.start:
                res.append(lres)
            else:
                res.append([min(lres[0], node.start), node.end])
                inserted = True
                break
        
        if not inserted:
            res.append([node.start, node.end])
        
        for rres in right_intervals:
            if rres[0] <= node.end:
                res[-1][1] = max(node.end, rres[1])
            else:
                res.append(rres)
        
        return res

이런생각을 어떻게하는거지?

일단 핵심 포인트는 다음과 같다.

• add할때 mid를 기준으로 end가 mid보다 작은건 왼쪽 subtree로, start가 mid보다 큰건 오른쪽 subtree로 가니까 왼쪽 subtree의 인터벌들하고 오른쪽 subtree의 인터벌들은 서로 겹칠일이 없다. 물론 현재 노드와는 겹칠수도 있고 아닐수도 있다.
• 왼쪽 subtree에서 현재 노드와 겹치는 인터벌들은 아무리 길어봤자 현재 노드보다 end가 길지 못하다. (add 방식때문에 보장된다.) 그래서 현재 노드와 겹치는 인터벌을 발견하면 start부분만 검사해서 확장해주면 된다.
• 오른쪽 subtree의 인터벌들이 현재 노드랑 겹치는 경우는 오른쪽 subtree 속 interval의 start가 현재 노드의 end보다 같거나 작은 경우다. 하지만 역시 add하는 방식때문에 start가 아무리 작아도 현재노드보다 작진 못하다. 그러니까 end만 누가 더 큰지 검사해서 확장해주면된다.

분석

	전체 데이터가 한 번에 주어지고 merged intervals를 한 번만 구하는 상황	N개의 데이터를 가지고 있는데 K개의 데이터가 들어오고 merged interval을 구하는 상황 (K는 충분히 작다고 가정)
Sorting Solution	시간 O(N log N) 공간 O(1) or O(N) (정답을 담을 공간도 공간복잡도로 계산한다면 N)	K개가 들어오기 전에 N개의 데이터를 가지고 있었다고 가정하면 시간 O(K + NlogN) 리스트에 하나 추가할때 O(1)이므로 K개 추가하면 O(K) + 정렬 O(N log N) 공간 O(N)
Interval Tree Solution	시간 O(N^2) add operation으로 하나씩 넣어야하므로 tree가 skewed된 상황에서 한번의 add가 O(N)이어서 worst case에 O(N^2) 공간 O(N)	K개가 들어오기 전에 N개의 데이터를 가지고 있었다고 가정하면 시간 O(KN + N) O(N)인 add를 K번하니까 KN 그리고 query한번 해서 N 공간 O(N)

한 번만 구하는 상황이면 트리 솔루션이 최악의 경우 N^2이라서 정렬 솔루션이 낫다.

하지만 스트림데이터를 가정한다면 (그리고 K가 작다면) k개 추가하고 결과값 얻을때마다 트리 솔루션이 O(N)에 가깝고 Sorting Solution이 O(NlogN)에 가까워서 트리 솔루션이 낫다.

만약 K가 N에 가깝게 커지면? (K = N)

Sorting Solution O(N + (2N) log (2N)) = O(N + N log N) = O(N log N)

Interval Tree Solution O(N^2 + N) = O(N^2)

정렬 솔루션이 더 좋아진다.

K가 log N에 가깝다면 (K = log N)

Sorting Solution O(logN + NlogN) = O( (N+1) log N ) = O(N log N)

Interval Tree Solution O(NlogN + N) = O( N * (logN + 1) ) = O(N log N)

둘이 또이또이하다.

 

그니까 K가 작을수록, 즉 수시로 확인할수록 트리솔루션이 좋고 K가 클수록(가끔씩 확인할수록) 정렬 솔루션이 좋다.