[Leetcode/파이썬] 56. Merge Intervals

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.

 

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

 

Constraints:

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

 

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x:x[0])
        res = []
        temp = [intervals[0][0], intervals[0][1]]
        for interval in intervals[1:] :
            if temp[0] <= interval[0] <= temp[1] :
                temp[0] = min(temp[0], interval[0])
                temp[1] = max(temp[1], interval[1])
            else :
                res.append(temp)
                temp = [interval[0], interval[1]]

        res.append(temp)
        return res

이 문제의 규칙은 가운데 들어갈 숫자를 잘 정하면 쉽게 해결할 수 있다. 가운데 들어갈 숫자는 interval[0], temp[1] 이 둘 중 하나가 될 것인데 intervals 를 interval[0] 기준으로 정렬하여 interval[0]를 사이에 두고 숫자를 갱신할 계획.

일단 정렬을 시켜주는데, 배열의 첫번째 숫자에 따라 앞으로 떙겨서 계산하기로 하였음. 이렇게 되면 가장 처음 interval로 초기화 했던 temp 배열과 현재 interval 간의 구간 비교를 하면 됨. interval[0]가 temp 사이나 처음 혹은 끝에 오게 될 경우, temp 에 구간을 합치게 되며, 이때는 min, max 메소드를 통하여 temp를 갱신하였다. 만약 interval[0]가 temp 구간에 속하지 않는다면, res에 temp를 추가 하고 현재의 interval로 초기화 한다. 아 이때는 temp = interval로 해도 되겠구나. 수정된 코드는 아래에 붙여넣겠다. for문을 다 돌고 나면 가장 마지막 interval은 temp에 남아있는 상태이다. 그래서 temp를 res에 추가하면 문제가 해결된다.

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x:x[0])
        res = []
        temp = [intervals[0][0], intervals[0][1]]
        for interval in intervals[1:] :
            if temp[0] <= interval[0] <= temp[1] :
                temp[0] = min(temp[0], interval[0])
                temp[1] = max(temp[1], interval[1])
            else :
                res.append(temp)
                temp = interval[:]

        res.append(temp)
        return res