[LeetCode 풀이/python] 57. Insert Interval (medium)

문제 설명: 겹치지 않는 구간(interval) 집합 intervals 가 주어졌을 때, 해당 집합에 새로운 구간을 삽입하시오 (필요하다면 병합도 수행). 각 구간들은 시작 시간을 기준으로 정렬되어 초기화 되어 있다.

 

(Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times.)

 

예시 1)

입력: intervals = [[1,3],[6,9]], newInterval = [2,5]  -->  출력: [[1,5],[6,9]]

 

예시 2)

입력: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]  -->  출력: [[1,2],[3,10],[12,16]]

설명: newInterval [4,8] 이 기존 배열의 [3,5],[6,7],[8,10] 과 오버랩 되기 때문

 

예시 3)

입력: intervals = [], newInterval = [5,7]  -->  출력: [[5,7]]

 

예시 4)

입력: intervals = [[1,5]], newInterval = [2,3]  -->  출력: [[1,5]]

 

예시 5)

입력: intervals = [[1,5]], newInterval = [2,7]  -->  출력: [[1,7]]

 

제한 조건:

• 0 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= intervals[i][0] <= intervals[i][1] <= 10^5
• 배열 intervals 는 intervals[i][0] 을 기준으로 오름차순 정렬되어 있음
• newInterval.length == 2
• 0 <= newInterval[0] <= newInterval[1] <= 10^5

 

 

 

------ * ------ * ------ * ------

 

[풀이 1안]

• 접근법
  • 일단 새로운 구간 newInterval 을 기존의 배열 intervals 에 추가하고 다시 정렬을 수행
  • 이전 구간이 끝나는 지점보다 새로운 구간의 시작 지점이 작거나 같으면 두 구간을 합병(merge) 하고, 아니면 이전 구간을 저장

 

• 코드 구현

 def insert(intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
    res = []
    start, end = -1, -1
    intervals.append(newInterval)
    intervals.sort()
        
    for i in intervals:
        if end < i[0]:
            res.append([start, end])
            start = i[0]
            end = i[-1]
        else:
            end = max(end, i[-1])
                
    res.append([start, end])
        
    return res[1:]

 

• 결과
  • 새로운 구간을 삽입하는 과정 자체는 O(n) 으로 이루어지나, 기존 배열에 newInterval 을 더해 정렬하는 과정에서 O(n log n) 이 소요됨  -->  총 O(n log n) 의 시간 복잡도 가짐

 

[풀이 2안]

• 접근법
  • sort 과정에서 O(n log n) 이 소요되므로... 미리 정렬하지 않고 O(n) 으로 풀 수 있는 방법이 없을까 고민해 봄
  • 기본적으로 intervals 배열을 탐색하되, 시작점 기준으로 newInterval 을 넣어야 하는 타이밍이 되면 newInterval 구간을 비교 대상으로 삼고 used flag 를 True 로 변경
  • 만약 배열을 끝까지 탐색했는데도 newInterval 을 탐색하지 않게 되는 경우는 별도로 처리

 

• 코드 구현

def insert(intervals, newInterval):
    res = []
    start, end = -1, -1

    used = False
    i = 0
    while i < len(intervals):
        if (not used) and (newInterval[0] <= intervals[i][0]):
            s, e = newInterval[0], newInterval[-1]
            used = True
            i -= 1
        else:
                s, e = intervals[i][0], intervals[i][-1]
    
            if s <= end:
                end = max(end, e)
            else:
                res.append([start, end])
                start, end = s, e    
            i += 1    
    
        if used:
            res.append([start, end])
        else:
            if newInterval[0] <= end:
                end = max(end, newInterval[-1])
                res.append([start, end])
            else:
                res.append([start, end])
                res.append(newInterval)

        return res[1:]

 

• 결과
  • 흠 시간 복잡도 O(n) 인데 왜 런타임이 더 긴 것인가... 오차 범위 안에 있는 듯...