Insert Interval

Q: Insert Interval의 시간 복잡도는 얼마인가요?

한 번의 순회로 해결하는 방법은 각 구간을 한 번씩 복사하거나 병합하므로 O(n) 시간이 걸리고, 최대 n+1 개의 구간으로 이루어진 결과를 저장하는 데 O(n) 공간을 사용합니다. 구간을 추가한 뒤 다시 정렬하는 데는 O(n log n) 이 걸립니다.

Q: Insert Interval은 Merge Intervals와 어떻게 다른가요?

구간 병합은 어떤 구간이든 다른 구간과 겹칠 수 있는 정렬되지 않은 목록에서 시작하므로 먼저 정렬합니다. 여기서는 목록이 정렬되어 있고 기존 구간끼리는 절대 맞닿지 않으므로 새 구간만 병합을 유발할 수 있으며, 병합되는 구간들은 하나의 연속된 구간을 이룹니다. 한 번 순회하는 것으로 충분합니다.

Q: 두 구간이 겹치는지 어떻게 확인하나요?

[a, b] 와 [c, d] 는 a ≤ d 이고 c ≤ b 일 때만 한 점을 공유합니다. 이 문제에서 원하는 대로 [2, 4] 와 [4, 8] 처럼 맞닿는 구간도 겹치는 것으로 계산합니다. 맞닿는 구간을 겹치지 않게 하려면 a < d 와 c < b 를 사용하세요.

보통구간

+10

시작값 기준으로 정렬된 구간을 두 배열로 받습니다. 구간 i는 [starts[i], ends[i]]이며, 서로 겹치거나 맞닿는 구간은 없습니다. 새 구간 [newStart, newEnd]를 삽입하고, 겹치거나 맞닿는 모든 구간과 병합한 뒤, 시작값 기준으로 정렬된 모든 구간을 [start, end] 쌍으로 반환하세요.

한 구간의 끝점이 다른 구간의 시작점과 같으면 구간이 맞닿습니다. 예를 들어 [2, 4]와 [4, 8]이 그렇고, 맞닿는 구간은 병합됩니다. [1, 2]와 [3, 4]는 공통점이 없으므로 서로 분리된 상태로 유지됩니다.

함수

insertInterval(starts: integer-array, ends: integer-array, newStart: integer, newEnd: integer) → integer-2d-array

startsinteger-array: 각 구간의 시작점, 오름차순으로
endsinteger-array: 각 구간의 끝, 이에 대응하는 시작점
newStartinteger: 삽입할 구간의 시작
newEndinteger: 삽입할 구간의 끝
반환값integer-2d-array: 삽입 후의 구간들을 [start, end] 쌍으로 나타내고, start를 기준으로 정렬합니다

제약 조건

1 ≤ starts.length == ends.length ≤ 2000
0 ≤ starts[i] ≤ ends[i] ≤ 10⁵
ends[i] < starts[i+1]: 구간은 시작 시점을 기준으로 정렬되어 있으며, 어떤 두 구간도 겹치거나 맞닿지 않습니다.
0 ≤ newStart ≤ newEnd ≤ 10⁵

예제

입력: starts = [1, 5, 10, 15]ends = [3, 7, 12, 18]newStart = 6newEnd = 11
출력: [[1, 3], [5, 12], [15, 18]]
설명: [6, 11]은 [5, 7] 및 [10, 12]와 겹치므로 세 구간은 [5, 12]가 됩니다. [1, 3]은 6 전에 끝나고 [15, 18]은 12 뒤에 시작하므로 둘 다 그대로 유지됩니다.

입력: starts = [2, 8]ends = [4, 9]newStart = 4newEnd = 8
출력: [[2, 9]]
설명: [4, 8]은 4에서 [2, 4]와 맞닿고 8에서 [8, 9]와 맞닿으므로, 세 구간이 모두 합쳐져 [2, 9]가 됩니다.

입력: starts = [1, 9]ends = [2, 10]newStart = 5newEnd = 6
출력: [[1, 2], [5, 6], [9, 10]]
설명: [5, 6]은 2와 9 사이의 빈틈에 있으며 어느 쪽 이웃과도 닿지 않으므로, 그 사이에 끼워 넣으면 병합되는 항목이 없습니다.

후속 질문

많은 구간을 연이어 삽입한다면, 각 삽입에 O(log n)에 삼켜지는 기존 구간마다 한 단계씩 더한 비용이 들도록 구간을 어떻게 저장하겠습니까?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

기존 구간은 정렬되어 있고 서로 떨어져 있으므로, 새 구간만 병합을 일으킬 수 있습니다. 따라서 목록은 세 부분으로 나뉩니다. 새 구간이 시작되기 전에 끝나는 구간, 새 구간과 겹치거나 맞닿는 구간, 새 구간이 끝난 뒤에 시작하는 구간입니다. 첫 번째 부분을 복사하고, 가운데 부분을 하나의 구간으로 합친 다음, 마지막 부분을 복사합니다. 한 번 순회하면 되며 정렬은 필요 없습니다.

그것을 추가하고 모든 것을 다시 병합하세요

핵심 아이디어

병합 구간을 재사용하세요: 새 구간을 추가하고, n+1개의 모든 구간을 시작점 기준으로 정렬한 다음, 마지막으로 병합된 구간을 유지하면서 순회합니다. 정렬 후에는 각 구간이 바로 앞 그룹과만 겹칠 수 있으므로, 다음 구간의 시작점이 유지 중인 끝점 이하이면 끝점을 늘립니다. 그렇지 않으면 간격이 생기고 새 구간이 시작됩니다.

정렬에는 한 곳에서 순서가 어긋난 목록을 바로잡는 데 O(n log n)의 비용이 들며, 기존 구간끼리는 서로 병합되지 않는다는 점도 고려하지 않습니다.

알고리즘

모든 시작점에 해당하는 끝점을 짝지어 [newStart, newEnd]를 목록에 추가합니다.
시작점을 기준으로 구간을 정렬합니다.
순서대로 살펴보면서 마지막으로 병합된 구간을 유지합니다.
다음 시작점이 유지 중인 끝점 이하라면, 유지 중인 끝점을 두 끝점 중 더 큰 값으로 설정합니다.
그렇지 않으면 다음 구간을 새로운 병합 구간으로 추가합니다. 병합된 목록을 반환합니다.

def insertInterval(starts, ends, newStart, newEnd):
    intervals = list(zip(starts, ends))
    intervals.append((newStart, newEnd))
    intervals.sort()
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)  # overlaps or touches: stretch
        else:
            merged.append([start, end])  # a real gap: a new interval begins
    return merged

세 부분으로 이루어진 한 번의 패스

핵심 아이디어

목록은 정렬되어 있고 구간들은 서로 떨어져 있으므로, 새 구간과 만나는 구간들은 하나의 끊기지 않는 연속 구간을 이룹니다. 이 연속 구간 앞에 있는 모든 구간은 ends[i] < newStart를 만족합니다. 즉, 새 구간이 시작되기 전에 끝납니다. 조건을 엄격하게 비교하는 이유는 구간이 newStart에서 정확히 끝나면 새 구간과 맞닿으므로 병합해야 하기 때문입니다.

연속 구간 안에서 starts[i] ≤ mergedEnd를 만족하는 구간은 만들고 있는 구간과 겹치거나 맞닿으므로, 시작점은 더 작은 값으로, 끝점은 더 큰 값으로 넓힙니다. mergedEnd보다 뒤에서 시작하는 첫 구간에서 연속 구간이 끝납니다. 그 이후의 모든 구간은 더 오른쪽에서 시작하기 때문입니다. 연속 구간이 비어 있으면 새 구간을 그대로 추가합니다. 첫 번째 예제에서는 [1, 3]을 복사하고, [5, 7]과 [10, 12]가 [6, 11]을 [5, 12]로 넓히며, [15, 18]을 복사합니다. 각 구간은 한 번씩만 확인합니다. 시간 복잡도는 O(n)이고, 결과를 제외하면 추가 메모리를 사용하지 않습니다.

알고리즘

ends[i] < newStart인 동안 구간을 결과에 복사합니다.
mergedStart = newStart와 mergedEnd = newEnd를 설정합니다.
starts[i] ≤ mergedEnd인 동안 mergedStart를 더 작은 시작값으로, mergedEnd를 더 큰 끝값으로 설정하고 다음으로 넘어갑니다.
[mergedStart, mergedEnd]를 추가합니다.
남은 구간을 복사하고 결과를 반환합니다.

def insertInterval(starts, ends, newStart, newEnd):
    n = len(starts)
    result = []
    i = 0
    # 1. Intervals that end before the new one starts stay as they are.
    while i < n and ends[i] < newStart:
        result.append([starts[i], ends[i]])
        i += 1
    # 2. Intervals that overlap or touch the new one fold into it.
    mergedStart, mergedEnd = newStart, newEnd
    while i < n and starts[i] <= mergedEnd:
        mergedStart = min(mergedStart, starts[i])
        mergedEnd = max(mergedEnd, ends[i])
        i += 1
    result.append([mergedStart, mergedEnd])
    # 3. Intervals that start after the merged one ends stay as they are.
    while i < n:
        result.append([starts[i], ends[i]])
        i += 1
    return result

함정과 경계 사례

겹치는 구간에 대한 부등호를 잘못 사용함. 첫 번째 루프에서 ends[i] ≤ newStart를 사용하거나 두 번째 루프에서 starts[i] < mergedEnd를 사용하면 [2, 4]와 [4, 8]은 서로 분리된 상태로 남습니다. 첫 번째 검사는 엄격하고, 두 번째 검사는 그렇지 않습니다.
mergedEnd + 1과 비교함. 그러면 한 점도 공유하지 않는 [1, 2]와 [3, 4]가 합쳐집니다.
병합된 구간의 시작으로 newStart를 유지함. [6, 11]은 [5, 7] 내부에서 시작하므로 결과는 5에서 시작합니다.
새 구간이 다른 구간과 겹칠 때만 추가함. [5, 6]처럼 구간 사이의 빈 곳이나 양쪽 끝을 넘어서는 곳에 들어가면 중간 루프가 실행되지 않지만, 그래도 반드시 추가해야 합니다.
i < n을 확인하기 전에 starts[i]를 읽음. 새 구간이 마지막 구간을 넘어가면 인덱스가 끝을 벗어납니다.

자주 묻는 질문3

Insert Interval의 시간 복잡도는 얼마인가요?

한 번의 순회로 해결하는 방법은 각 구간을 한 번씩 복사하거나 병합하므로 O(n) 시간이 걸리고, 최대 n+1개의 구간으로 이루어진 결과를 저장하는 데 O(n) 공간을 사용합니다. 구간을 추가한 뒤 다시 정렬하는 데는 O(n log n)이 걸립니다.

Insert Interval은 Merge Intervals와 어떻게 다른가요?

구간 병합은 어떤 구간이든 다른 구간과 겹칠 수 있는 정렬되지 않은 목록에서 시작하므로 먼저 정렬합니다. 여기서는 목록이 정렬되어 있고 기존 구간끼리는 절대 맞닿지 않으므로 새 구간만 병합을 유발할 수 있으며, 병합되는 구간들은 하나의 연속된 구간을 이룹니다. 한 번 순회하는 것으로 충분합니다.

두 구간이 겹치는지 어떻게 확인하나요?

[a, b]와 [c, d]는 a ≤ d이고 c ≤ b일 때만 한 점을 공유합니다. 이 문제에서 원하는 대로 [2, 4]와 [4, 8]처럼 맞닿는 구간도 겹치는 것으로 계산합니다. 맞닿는 구간을 겹치지 않게 하려면 a < d와 c < b를 사용하세요.

def insertInterval(starts, ends, newStart, newEnd):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자들

starts = [1, 5, 10, 15]
ends = [3, 7, 12, 18]
newStart = 6
newEnd = 11

예상 출력

[[1, 3], [5, 12], [15, 18]]