leetcode medium : merge intervals

Merge Intervals - LeetCode

Merge Intervals - LeetCode

 

쉬워보이지만 실수하기 쉬운문제

 

먼저 정렬을 해서 임의의 원소 intervals[i]와 intervals[i+1]사이에

intervals[i][0] <= intervals[i+1][0]이 항상 성립하게 만들어야 한다.

안 그러면 매우 골치아파짐

문제 상수조건 보면 최대 10000개인걸로 봐서 O(N^2) 알고리즘은 사용할 수 없음. 그래서 N log N 안에 끝내야된다.

N log N 하면 역시 정렬이지 ㅋㅋ

 

그리고 현재 start~end 범위와 다음 원소의 start~end 범위를 비교해서 더 확장할 필요가 있으면 확장하고 둘이 겹치는 부분이 없으면 현재 start~end 범위를 result 리스트에 추가하면된다. 이때 다음 원소의 범위가 현재 범위에 포함될수도 있고 걸쳐져 있을 수도 있기 때문에 이를 잘 고려해서 코드를 짜자. 굵은 글씨 쳐놨다.

 

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        result = []
        
        intervals.sort()
        
        start = intervals[0][0]
        end = intervals[0][1]
        
        for i in range(1, len(intervals)):
            s = intervals[i][0]
            e = intervals[i][1]
            
            if s <= end:
                end = max(end, e)
            else:
                result.append([start, end])
                start = s
                end = e
                
        result.append([start, end])
            
        return result