LeetCode: Merge Intervals

intervals 주어진 배열에서 , 모든 겹치는 구간을 병합하고, 입력에 있는 모든 구간을 포함하는 겹치지 않는 구간의 배열을 반환합니다 .intervals[i] = [starti, endi]

 

예시 1:

입력: 간격 = [[1,3],[2,6],[8,10],[15,18]]
 출력: [[1,6],[8,10],[15,18]]
 설명: 간격 [1,3]과 [2,6]이 겹치므로 [1,6]으로 병합합니다.

예 2:

입력: 간격 = [[1,4],[4,5]]
 출력: [[1,5]]
 설명: 간격 [1,4]와 [4,5]는 겹치는 것으로 간주됩니다.

 

제약 조건:

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

오늘도 한문제 풀어보았다. 

 

일단 이 문제는 피지컬 문제인 것 같다. 

 

구현을 정말 잘 해야 풀 수 있는 문제인 것 같다. 

 

일단 처음에는 내가 아는 자료구조 문제는 아닌 것 같아 보였다. 단순 구현 문제라고 판단을 하고 풀었다.

 

일단 어떻게 해야 이 문제를 풀 수 있을까..?

 

나는 일단 그리디 방식으로 접근하려고 했다. 

 

먼저 interval의 0번째 항으로 interval들을 정렬한 후에 가장 앞( 첫 성분의 수가 가장 작은) interval을 사용하여 

merge하기로 했다. 

 

과연 될까? 생각해봤는데, n번째라고 가정했을 때, n-1번째 interval의 두 번째 성분과 n번째 시작 interval을 비교해야 interval이 병합되거나 병합되지 않을 때 merge list에 추가하여 다음 interval과 비교할 수 있게 된다.

 

말이 좀 어려워서 예시로 소개해 보겠다.

 

입력: 간격 = [[1,3],[2,6],[8,10],[15,18]]
 출력: [[1,6],[8,10],[15,18]]

 

이 상황을 생각해보자

일단 0번째 성분으로 잘 정렬된 것을 확인할 수 있다.

이때 3과 2를 비교 -> 포함이므로 합침 [1, 6] -> 6과 8을 비교 -> 불포함이기 때문에 [8, 10] 추가 -> 10과 15를 비교

-> 미포함이기 때문에 [15, 18]추가

 

하지만 정렬이 되어있지 않으면, 18과 3을 비교해야 한다. 근데 시작지점이 어떻게 되는지 알 수 없으므로 비교가 불가능해 지는 것!

 

따라서 정렬을 통해 이전 구간과 상관없이 끝의 성분을 통해 비교할 수 있도록 만드는 것이다. 

 

정렬을 통해 논리 구조를 하나 세운 셈인 것!

 

따라서 다음의 논리를 따를 수 있다.

 

1. 첫 성분으로 interval sort

2. merge = [] 정의 ( 결과 리스트 )

3. for interval in intervals -> interval을 하나씩 받아옴

4. 받아온 interval과 merge의 마지막 interval과 비교하여 합침 (단 merge가 비어있다면 interval을 merge에 그냥 추가)

5. 4를 반복

6. merge반환

 

 

 

---

 

구현코드

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: List[List[int]]
        """
        intervals.sort(key=lambda x:x[0])

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

        return merge