문제

• overlapping 하는 애들 다 merge 해라

풀이

• 일단 sort 해서 start 순으로 나열
• 나열 후, start[i+1] <= end[i]인 경우, overlap으로 판단
• end를 계속해서 max로 갱신
• 시간은 오래걸림,,, O(nlogn)

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        answer = []
        intervals.sort()
        semiAns = intervals[0]
        for start, end in intervals[1:]:
            if start <= semiAns[1]:
                # overlapped
                semiAns[1] = max(semiAns[1], end) # new interval's end can be bigger
            else:
                answer.append(semiAns.copy())
                semiAns = [start, end]
        answer.append(semiAns)
        return answer

예외 케이스로 고려한 것

1. [[1,1], [2,3], [4,7], [5,6]]
   뒤의 구간이 앞의 구간에 완전 들어간다
2. [[1,7], [2,5], [3,4]]
   뒤의 구간 모두가 앞의 구간에 포함된다 + 3개 구간 합쳐짐

결과

근데 다른 사람들 풀이도 나랑 비슷한데 왜 16.88% 밖에 안되는지 모르겠다...