Merge Intervals | LeetCode 803 | Python3 🐍

 

📄 목차

 

 

🤔 문제 : Merge Intervals | LeetCode 803

문제: https://leetcode.com/explore/interview/card/top-interview-questions-medium/110/sorting-and-searching/803/

배열로 주어진 범위(interval)들을 합치는 문제입니다.

 

예를들어 [1,3], [2,4]가 들어오면 -> [1,4] 로 합쳐집니다.

 

 

💡 풀이

접근 : interval이 겹치는 종류

일단 interval끼리 어떤 방식으로 겹칠 수 있을지 생각해보았습니다.

1. left overlapping : 새로 들어오는 interval의 왼쪽 범위가 기존에 있던 범위의 오른쪽에 겹쳐서 들어감

ex) 기존 : [1, 3]  신규: [2, 4] -> [1, 4]

2. right overlapping : 새로 들어오는 interval의 오른쪽 범위가 기존에 있던 범위의 왼쪽에 겹쳐서 들어감 

ex) 기존 : [2, 4]  신규: [1, 3] -> [1,4]

3. included : 새로 들어오는 interval이 기존 interval에 완전히 포함됨

ex) 기존: [1,4], 신규[2,3] -> [1,4]

4. overlap : 새로 들어오는 interval이 기존 interval을 완전히 포함함

ex) 기존: [2,3], 신규[1,4] -> [1,4]

 

이렇게 놓고 보니,

input을 정렬한 후 문제를 해결하면 2, 4번 케이스는 고려하지 않아도 되겠네요.

 

풀이 

from typing import List

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if len(intervals) == 1 : return intervals
        sorted_intervals = sorted(intervals, key=lambda d: d[0]) # [1]
        ret = [sorted_intervals[0]]
        for i in sorted_intervals[1:]:
            if i[0] > ret[-1][1]: ret.append(i)			# [2]
            elif i[1] > ret[-1][1]: ret[-1][1] = i[1]		# [3]
        return ret

[1] input을 interval 시작점 기준으로 정렬

ret 은 완성된 interval을 저장하여둠. ret의 interval들을 겹치는 부분이 없게 유지됨. 

[2] 새로 들어올 interval이, 지금까지 만들어진 interval의 가장 마지막 요소보다 더 뒤에서 시작하면 그냥 append

ex) 기존 : [1, 3] 신규:  [5, 6]

[3] 새로 들어올 interval이, 지금까지 만들어진 interval의 가장 마지막 요소보다 더 앞에서 시작하면, 기존 interval에 합침. 이 때 새로운 interval이 기존 마지막 Interval보다 뒤에서 끝나면 기존 Interval값을 업데이트

* 참고) [1]에서 input을 시작점 기준으로 정렬하였으므로, 신규 interval의 시작값이 기존 interval의 시작값보다 작은 경우는 없음

 

Time Complexity
정렬 : O(NlogN)
interval구성 : O(N)
=> 최종 O(NlogN)