Leetcode 9월 Day12

문제 설명 - *중첩되지 않는 간격 집합이 주어지면 간격에 새 간격을 삽입합니다(필요한 경우 병합).

간격이 처음에 시작 시간*에 따라 정렬되었다고 가정할 수 있습니다.

예시 -
""
입력: 간격 = [[1,3],[6,9]], newInterval = [2,5]
출력: [[1,5],[6,9]]
""
내 초기 접근 방식 - 간격 배열이 각 간격의 시작을 기준으로 정렬 된 상태로 유지되도록 위치에 newInterval를 삽입하십시오.
newInterval을 삽입한 후 가능한 모든 간격을 병합할 수 있습니다.
해결책

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        if len(intervals) == 0:
            return [newInterval]
        intervals.append(newInterval)
        intervals = sorted(intervals, key = lambda x : x[0])
        # now merge the intervals
        i = 1
        while i < len(intervals):
            p_i = intervals[i-1]
            c_i = intervals[i]
            if p_i[0] <= c_i[0] and c_i[0] <= p_i[-1]:
                intervals[i-1] = [p_i[0], max(c_i[-1], p_i[-1])]
                del intervals[i]
            else:
                i += 1
        return intervals

TC - 정렬 및 삭제 때문에 O(nlogn + n^2).

어떻게 최적화할 수 있습니까 ??

이진 검색을 사용하여 인덱스를 결정할 수 있습니다.

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        if len(intervals) == 0:
            return [newInterval]
        intervals.append(newInterval)
        intervals = sorted(intervals, key = lambda x : x[0])
        lo = 0
        hi = len(intervals) - 1
        idx = 0
        while lo < hi:
            mid = (lo + hi)//2
            if intervals[mid][0] <= newInterval[0]:
                idx = max(idx, mid)
                lo = mid + 1
            else:
                hi = mid - 1
        intervals.insert(idx + 1, newInterval)
        # now merge the intervals
        i = 1
        while i < len(intervals):
            p_i = intervals[i-1]
            c_i = intervals[i]
            if p_i[0] <= c_i[0] and c_i[0] <= p_i[-1]:
                intervals[i-1] = [p_i[0], max(c_i[-1], p_i[-1])]
                del intervals[i]
            else:
                i += 1
        return intervals