Insert Interval

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

한 번의 순회로 해결하는 방법은 O(n) 시간에 실행됩니다. 각 구간은 정확히 한 번 복사되거나 병합됩니다. 결과에는 최대 n+1 개의 구간이 포함되므로 O(n) 공간이 필요하며, 그 외에는 입력 크기에 따라 증가하는 것이 없습니다. 구간을 추가한 뒤 다시 정렬하면 대신 O(n log n) 이 걸립니다.

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

Merge Intervals는 어떤 구간이든 다른 구간과 겹칠 수 있는 정렬되지 않은 목록에서 시작하므로 먼저 정렬해야 합니다. Insert Interval에서는 목록이 이미 정렬되어 있고 기존 구간들은 서로 겹치지 않으므로 새 구간만 병합을 일으킬 수 있습니다. 새 구간이 병합되는 구간들은 끊기지 않은 하나의 연속 구간을 이루므로 정렬 없이 한 번만 순회해도 충분합니다.

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

구간 [a, b] 와 [c, d] 는 a ≤ d 이고 c ≤ b 일 때에만 적어도 한 점을 공유합니다. 따라서 [2, 4] 와 [4, 8] 처럼 맞닿는 구간도 겹치는 것으로 셉니다. 이 문제에서 원하는 방식입니다. 맞닿는 구간을 서로 분리해야 한다면 대신 a < d 와 c < b 를 사용하면 됩니다.

Q: 이진 탐색을 사용하면 Insert Interval을 더 빠르게 만들 수 있을까요?

병합된 구간이 시작하고 끝나는 위치를 이진 탐색으로 O(log n) 에 찾을 수 있습니다. 시작점과 끝점이 모두 정렬되어 있기 때문입니다. 하지만 이 함수는 여전히 새 목록을 반환하며, 변경되지 않은 구간을 여기에 복사하는 데 O(n) 이 걸립니다. 따라서 전체 시간 복잡도는 여전히 O(n) 입니다. 구간이 균형 트리처럼 복사 없이 범위를 삭제하고 삽입할 수 있는 자료구조에 저장되어 있을 때 이진 탐색이 효과를 발휘합니다.

보통구간

+10

시작점 기준으로 정렬된 구간 목록이 주어집니다. 목록은 길이가 같은 두 배열로 표현되며, 구간 i는 [starts[i], ends[i]]입니다. 서로 겹치거나 맞닿는 구간은 없습니다. 새 구간 하나 [newStart, newEnd]도 주어집니다. 이 구간을 삽입하고, 겹치거나 맞닿는 모든 구간과 병합한 다음, 모든 구간을 시작점 기준으로 정렬된 [start, end] 쌍의 2차원 배열로 반환하세요.

한 구간의 끝점이 다른 구간의 시작점과 같으면 두 구간은 맞닿습니다. 예를 들어 [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 사이의 간격에 놓여 있고 어느 쪽 이웃과도 닿지 않으므로, 그 사이에 삽입되며 병합되는 것은 없습니다.

제출 시 숨은 테스트 +20개

후속 질문

같은 목록에 새 구간을 하나씩 여러 개 삽입한다고 가정해 보세요. 각 삽입의 비용이 O(log n)에, 삽입되는 구간이 포함하는 기존 구간마다 한 단계씩 더해지도록 하려면 구간을 어떻게 저장해야 할까요?

힌트

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

3개 중 0개 열림

풀이

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

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

핵심 아이디어

Merge Intervals를 풀어 봤다면, 여기서 그 풀이를 재사용할 수 있습니다. 새 구간을 목록에 넣고, 모든 n+1개 구간을 시작점 기준으로 정렬한 다음 병합합니다. 정렬한 뒤에는 각 구간이 바로 앞 그룹과만 겹칠 수 있으므로, 마지막으로 병합한 구간을 유지하면서 목록을 순회하면 됩니다. 다음 구간의 시작점이 그 구간의 끝점 이하라면 끝점을 늘립니다. 그렇지 않으면 실제로 간격이 있는 것이므로 새 구간이 시작됩니다.

첫 번째 예제에 적용해 봅시다. 목록은 [1, 3], [5, 7], [6, 11], [10, 12], [15, 18]이 됩니다. 5는 3보다 크므로 [1, 3]은 그대로 남습니다. 6은 7 이하이므로 [5, 7]은 [5, 11]로 늘어납니다. 10은 11 이하이므로 [5, 12]로 늘어납니다. 15는 12보다 크므로 [15, 18]이 새 구간으로 시작됩니다.

이 방법은 올바르고, 구간이 2000개일 때도 빠르게 실행됩니다. 하지만 주어진 사실 두 가지를 무시합니다. 목록은 이미 정렬되어 있고, 기존 구간끼리는 병합되지 않는다는 점입니다. 한 곳만 순서가 어긋난 목록을 다시 정렬하는 데 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

세 부분으로 나눈 한 번의 패스

핵심 아이디어

인덱스 i를 사용해 목록을 한 번 훑으며 세 구간으로 나눕니다. 먼저, ends[i] < newStart인 모든 구간은 새 구간이 시작되기 전에 끝나므로 새 구간과 겹치는 점이 없습니다. 이 구간을 결과에 복사합니다. 여기서 <를 사용하는 이유는 구간이 newStart에서 정확히 끝나면 새 구간과 맞닿아 병합해야 하기 때문입니다.

둘째, starts[i] ≤ mergedEnd인 모든 구간은 만들고 있는 구간과 겹치거나 맞닿습니다. 이를 병합합니다. mergedStart는 시작점 중 더 작은 값이 되고 mergedEnd는 끝점 중 더 큰 값이 됩니다. 이 구간에 속한 구간들은 목록이 정렬되어 있으므로 서로 이어져 있습니다. 어떤 구간의 시작점이 mergedEnd보다 뒤에 오면, 그 이후의 모든 구간은 시작점이 더 오른쪽에 있으므로 그 뒤의 구간은 더 이상 병합될 수 없습니다. 병합된 구간을 추가합니다. 이 단계는 구간이 비어 새 구간이 단독으로 들어가는 경우도 처리합니다.

셋째, 남은 모든 구간을 복사합니다. 이 구간들은 병합된 구간이 끝난 뒤에 시작하며, 서로 이미 떨어져 있습니다.

첫 번째 예제를 따라가 봅시다. [1, 3]은 6보다 먼저 끝나므로 복사합니다. [5, 7]은 5에서 시작하며, 이는 11 이하이므로 병합된 구간은 [5, 11]이 됩니다. [10, 12]는 10에서 시작하며, 이는 11 이하이므로 [5, 12]가 됩니다. [15, 18]은 12보다 뒤에서 시작하므로 [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]은 서로 분리된 채로 남습니다. 맞닿은 구간은 병합되므로 첫 번째 검사는 엄격 부등식이고 두 번째 검사는 그렇지 않습니다.
그저 인접해 보이는 구간을 병합하는 경우. [1, 2]와 [3, 4]는 공통점을 공유하지 않으므로 mergedEnd + 1과 비교하면 분리된 채로 있어야 할 구간이 병합됩니다.
병합된 시작점으로 newStart를 그대로 사용하는 경우. 새 구간이 기존 구간 안에서 시작하면, [6, 11]이 [5, 7] 안에서 시작하는 것처럼 결과는 5에서 시작합니다. 두 시작점 중 더 작은 값을 사용하세요.
새 구간이 다른 구간과 겹칠 때만 추가하는 경우. 새 구간이 모든 구간보다 앞이나 뒤에 오거나 구간 사이의 빈 곳에 놓이면 가운데 루프는 실행되지 않지만, 새 구간은 그래도 추가해야 합니다.
i < n인지 확인하기 전에 starts[i] 또는 ends[i]를 읽는 경우. 새 구간이 마지막 구간을 넘어가면 인덱스가 배열의 끝을 벗어납니다.

자주 묻는 질문4

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

한 번의 순회로 해결하는 방법은 O(n) 시간에 실행됩니다. 각 구간은 정확히 한 번 복사되거나 병합됩니다. 결과에는 최대 n+1개의 구간이 포함되므로 O(n) 공간이 필요하며, 그 외에는 입력 크기에 따라 증가하는 것이 없습니다. 구간을 추가한 뒤 다시 정렬하면 대신 O(n log n)이 걸립니다.

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

Merge Intervals는 어떤 구간이든 다른 구간과 겹칠 수 있는 정렬되지 않은 목록에서 시작하므로 먼저 정렬해야 합니다. Insert Interval에서는 목록이 이미 정렬되어 있고 기존 구간들은 서로 겹치지 않으므로 새 구간만 병합을 일으킬 수 있습니다. 새 구간이 병합되는 구간들은 끊기지 않은 하나의 연속 구간을 이루므로 정렬 없이 한 번만 순회해도 충분합니다.

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

구간 [a, b]와 [c, d]는 a ≤ d이고 c ≤ b일 때에만 적어도 한 점을 공유합니다. 따라서 [2, 4]와 [4, 8]처럼 맞닿는 구간도 겹치는 것으로 셉니다. 이 문제에서 원하는 방식입니다. 맞닿는 구간을 서로 분리해야 한다면 대신 a < d와 c < b를 사용하면 됩니다.

이진 탐색을 사용하면 Insert Interval을 더 빠르게 만들 수 있을까요?

병합된 구간이 시작하고 끝나는 위치를 이진 탐색으로 O(log n)에 찾을 수 있습니다. 시작점과 끝점이 모두 정렬되어 있기 때문입니다. 하지만 이 함수는 여전히 새 목록을 반환하며, 변경되지 않은 구간을 여기에 복사하는 데 O(n)이 걸립니다. 따라서 전체 시간 복잡도는 여전히 O(n)입니다. 구간이 균형 트리처럼 복사 없이 범위를 삭제하고 삽입할 수 있는 자료구조에 저장되어 있을 때 이진 탐색이 효과를 발휘합니다.

Python

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]]