[LeedCode] 56. Merge Intervals 파이썬 Medium

문제 해석:

배열에 각 시작점, 종료점을 가진 값들이 저장되어 있다. 
겹쳐져 있는 구간들을 합치고, 겹치지 않는 모든 간격들은 배열에 넣어 반환한다.

문제 해설:

1. 주어지는 점들은 길이가 모두 다르기 때문에, 간격마다 모두 확인을 해야한다.
처음나온 간격이 다음 간격보다 클수도, 작을수도, 혹은 모두 포함될 수 도 있다.
2. 간격들을 오름차순으로 정렬하여, 하나씩 저장해나가야한다.
3. 새로만든 리스트가 비어있으면 바로 넣는다.
4. 리스트 가장 뒤의 간격의 끝 숫자가 새로 확인되는 간격 첫 숫자보다 작을 경우 리스트에 넣는다.
5. 3번과 4번이 아니라면 간격이 겹친다. 리스트는 이미 정렬되어있기 때문에
마지막의 간격 끝점과 새로 확인될 간격의 시작점을 비교하여 큰 값을 끝점으로 갱신한다.

 

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] overlaps, 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])
        merged = []
        for start, end in intervals:
        	# 리스트에 값이 없으면 넣기.
            if not merged:
                merged.append([start, end])
            # 리스트 마지막 끝값과 들어올 값의 시작점 비교해서 겹치지 않는 간격이면 리스트에 추가
            elif merged[-1][1] < start:
                merged.append([start, end])
            # 겹치는 간격이면, 끝점끼리 비교해서 값 갱신
            else:
                merged[-1][1] = max(merged[-1][1], end)
        return merged