[Sorting] 56. Merge Intervals

https://leetcode.com/problems/merge-intervals/description/

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]) #정렬기준 key를 오름차순으로 정렬 시, start=x[0]을 기준으로 함

        result = []
        if intervals:
            cur = intervals[0] #초기값 설정 ex cur = [1,3]

            for next in intervals[1:]: #start = 1부터 순차적으로 탐색

                if next[0] <= cur[1]:
                    cur[1] = max(cur[1], next[1]) #병합
                else:
                    result.append(cur) #그냥 추가
                    cur = next #다음 [start, end]요소 받기
            result.append(cur) #순차적으로 next를 result에 추가
        
        return result

---

 

 

리스트의 요소 x에 대해 x[0]=start를 기준으로 오름차순 정렬하겠다.

 

 

오름차순

intervals.sort(key=lambda x: x[0])

내림차순

intervals.sort(key=lambda x: x[0], reverse=True)

 

x[1] 인 end를 기준으로 정렬할 시 다음과 같이 될 수 있다.

 

 

cur : list내에서 현재 가리키고 있는 [start, end] 요소

next : 다음 [start, end] 요소