[DSA][Intervals] 02. Merge Intervals

LeetCode 56

 

02. Merge Intervals

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

 

 

[질문하기]

- intervals에 빈 배열이 들어올 수 있나요? NO

 

[아이디어]

- intervals를 시작 시점 기준으로 정렬하여 중복된 구간을 병합한다.

 

 

[풀이 1] intervals

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        res = []

        oldS, oldE = intervals[0][0], intervals[0][1]
        for interval in intervals:
            if oldE < interval[0]:
                res.append([oldS, oldE])
                oldS, oldE = interval[0], interval[1]
            else:
                oldS, oldE = min(oldS, interval[0]), max(oldE, interval[1])

        res.append([oldS, oldE])
        return res

중복된 간격이 있는지 확인하고 순차적으로 병합하기 위해 intervals를 시작 시점 기준 오름차순으로 정렬한다.

• 새로운 interval의 Start 값이 이전 interval의 End 값보다 작거나 같으면, 두 간격은 겹친다고 볼 수 있다. 이때, 두 간격을 병합해서 Start는 작은 값으로, End는 큰 값으로 업데이트한다.
• 반대로, 새로운 interval의 Start 값이 이전 interval의 End 값보다 크다면, 두 간격은 겹치지 않기 때문에 이전 간격을 결과 리스트 res에 추가하고, 현재 interval을 새로운 기준으로 설정한다.

이렇게 하면 병합된 간격들만 남게 되고, 최종적으로 res에 중복되지 않는 간격들을 모두 모을 수 있다.

 

 

⏱️ 시간복잡도

배열을 정렬한 후 순회하므로, 시간 복잡도는 O(nlogn)이다.

🧠 공간복잡도

추가적으로 사용하는 공간 없이 결과를 담기 위한 배열만을 사용하므로 공간 복잡도는 O(n)이다.