Merge Intervals

Q: Merge Intervals의 시간 복잡도는 얼마인가요?

정렬 및 스윕 솔루션은 n개의 구간에 대해 O(n log n) 시간에 실행됩니다. 정렬에는 O(n log n)이 걸리고 스윕에는 O(n)이 걸립니다. 정렬된 쌍과 결과를 위해 O(n)의 추가 공간을 사용합니다.

Q: 구간을 끝이 아니라 시작 기준으로 정렬하는 이유는 무엇인가요?

시작점 기준으로 정렬하면 구간은 현재 만들고 있는 그룹과만 겹칠 수 있으므로, 그 그룹의 끝점과 한 번 비교하면 모든 것이 결정됩니다. 끝점 기준으로 정렬하면 나중 구간의 시작점이 이미 닫은 그룹보다 앞설 수 있습니다. [5, 6] 이 [1, 10] 보다 먼저 오며, 앞에서부터 순회하면 시작점으로 5를 잘못 유지하게 됩니다.

Q: 추가 공간 없이 구간을 병합할 수 있나요?

네, 입력을 변경해도 된다면 가능합니다. 구간을 제자리에서 정렬한 다음, 병합된 각 구간을 같은 배열의 앞쪽에 덮어 쓰고 마지막으로 쓴 구간의 인덱스를 유지하세요. 시간 복잡도는 O(n log n)으로 유지되며, 추가 공간은 사용하는 언어의 정렬 기능이 필요로 하는 공간뿐입니다.

보통구간 정렬

+10

시작부터 끝까지의 정수 범위인 구간들이 주어집니다. 겹치는 모든 구간을 전체 범위를 포함하는 하나의 구간으로 병합하고, 병합된 구간을 시작점 기준으로 정렬하여 반환하세요. [1, 4]와 [4, 5]처럼 서로 맞닿기만 하는 구간도 겹치는 것으로 간주합니다.

구간은 길이가 같은 두 배열로 주어집니다. 구간 i는 [starts[i], ends[i]]입니다. [start, end] 쌍의 목록인 2차원 배열을 반환하세요.

함수

mergeIntervals(starts: integer-array, ends: integer-array) → integer-2d-array

startsinteger-array: 각 구간의 시작
endsinteger-array: 각 구간의 끝, 시작과 같은 인덱스에
반환값integer-2d-array: 시작을 기준으로 정렬된 [start, end] 쌍 형태의 병합된 구간

제약 조건

1 ≤ starts.length == ends.length ≤ 10⁴
0 ≤ starts[i] ≤ ends[i] ≤ 10⁴
구간은 순서에 관계없이 주어집니다.
끝점에서만 맞닿는 구간도 겹치는 것으로 간주합니다.

예제

입력: starts = [5, 1, 12, 3]ends = [7, 4, 14, 6]
출력: [[1, 7], [12, 14]]
설명: 시작 순서대로 보면 [1, 4]는 [3, 6]과 겹치고, [3, 6]은 [5, 7]과 겹치므로 세 구간은 [1, 7]이 됩니다. [12, 14]는 7 이후에 시작하므로 따로 유지됩니다.

후속 질문

구간은 이미 병합되어 시작점 기준으로 정렬된 상태로 주어지며, 새로운 구간 하나를 추가해야 합니다. 다시 정렬하지 않고 O(n) 시간에 병합된 목록을 반환할 수 있나요?

풀이

어떤 순서로든 쌍을 병합하려면 여러 번 순회해야 합니다. 각 병합은 구간을 넓혀 이미 확인한 구간에 닿을 수 있게 하기 때문입니다. 대신 시작점을 기준으로 정렬하세요. 그러면 구간은 현재 만들고 있는 그룹과만 겹칠 수 있으므로 한 번만 순회해도 작업을 끝낼 수 있습니다.

변화가 없을 때까지 겹치는 쌍을 병합합니다

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

[a, b]와 [c, d] 구간은 c ≤ b이고 a ≤ d일 때 겹치며, [min(a, c), max(b, d)]는 두 구간을 모두 포함합니다. 병합할 때마다 구간 하나가 제거되므로 이 과정은 멈추며, 전체 구간을 한 번 훑었을 때 겹치는 구간이 없으면 남은 구간 중 어떤 두 구간도 점을 공유하지 않습니다. 한 번 훑는 것만으로는 충분하지 않습니다. 병합된 구간은 더 넓어져서, 이제는 그보다 작은 부분이 해당 순회에서 앞서 비교했던 구간에 닿을 수 있습니다.

한 번의 순회에서는 약 n²/2개의 쌍을 비교하며, 최대 n번의 순회가 필요할 수 있습니다. 즉 O(n³)입니다. 구간 10^4개를 한 번 훑는 것만으로도 이미 5 × 10^7번의 비교가 필요합니다.

알고리즘

starts와 ends를 복사하고, 활성 구간의 개수 n을 유지합니다.
각 구간 i를 그 뒤에 오는 모든 구간 j와 비교합니다. 서로 겹치면 i를 늘려 j를 포함하고, 마지막 활성 구간을 j 슬롯으로 옮긴 다음 n을 1 줄입니다.
병합한 뒤에는 j 슬롯을 다시 확인합니다. 이제 그 자리에 다른 구간이 있기 때문입니다.
병합이 일어나지 않는 패스가 나올 때까지 패스를 반복합니다.
활성 시작값을 각각 해당 끝값과 짝지어 시작값을 기준으로 쌍을 정렬한 다음 반환합니다.

def mergeIntervals(starts, ends):
    s = list(starts)
    e = list(ends)
    n = len(s)
    changed = True
    while changed:
        changed = False
        i = 0
        while i < n:
            j = i + 1
            while j < n:
                if s[j] <= e[i] and s[i] <= e[j]:
                    # Intervals i and j overlap: interval i absorbs interval j.
                    s[i] = min(s[i], s[j])
                    e[i] = max(e[i], e[j])
                    # Move the last interval into slot j and drop the last slot.
                    n -= 1
                    s[j] = s[n]
                    e[j] = e[n]
                    changed = True
                else:
                    j += 1
            i += 1
    return sorted([s[k], e[k]] for k in range(n))

시작점 기준으로 정렬한 뒤 한 번 훑기

핵심 아이디어

시작점을 기준으로 정렬한 후에는 다음 구간이 마지막 그룹의 끝인 e보다 이른 시점에 시작하지 않습니다. 시작점이 e보다 작거나 같으면 그룹과 겹치거나 맞닿으므로 그룹에 합쳐지고, e는 두 끝점 중 더 큰 값이 됩니다. 시작점이 e보다 크면 이후 구간도 그룹까지 거슬러 올라올 수 없습니다. 이후 구간은 더 오른쪽에서 시작하기 때문입니다. 그룹이 끝나고, 해당 구간은 새 그룹을 시작합니다.

정렬에는 O(n log n)이 걸리고, 스윕 과정에서는 각 구간을 한 번씩 방문합니다. 그룹은 왼쪽에서 오른쪽으로 닫히므로 결과는 시작점 기준으로 정렬됩니다.

알고리즘

각 시작을 해당 끝과 짝지으세요. 구간 i는 [starts[i], ends[i]]입니다.
쌍을 시작 값 기준으로 정렬하세요.
정렬된 쌍을 순회하세요. 결과가 비어 있거나 쌍의 시작 값이 마지막으로 병합된 구간의 끝보다 크면, 해당 쌍을 새 구간으로 추가하세요.
그렇지 않으면 마지막으로 병합된 구간의 끝을 그 구간의 끝과 해당 쌍의 끝 중 더 큰 값으로 설정하세요.
병합된 목록을 반환하세요.

def mergeIntervals(starts, ends):
    intervals = sorted(zip(starts, ends))
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:
            if end > merged[-1][1]:
                merged[-1][1] = end
        else:
            merged.append([start, end])
    return merged

함정과 경계 사례

≤ 대신 <로 비교하는 경우. [1, 4]와 [4, 5]처럼 맞닿은 구간은 병합해야 합니다.
끝점을 두 값 중 큰 값이 아니라 새 구간의 끝점으로 설정하는 경우. [1, 10] 다음에 [2, 3]이 와도 [1, 10]으로 유지해야 합니다.
starts만 따로 정렬한 다음 새 위치의 ends를 읽으면, 한 시작점에 다른 구간의 끝점이 연결됩니다. 먼저 쌍으로 묶거나 인덱스를 정렬하세요.
마지막으로 병합된 구간이 아니라 이전 입력 구간과 비교하는 경우. [1, 10], [2, 3], [4, 5]에서 세 번째 구간은 [2, 3]과 맞닿지는 않지만 [1, 10] 안에 있습니다.
C에서는 *returnSize를 병합된 구간의 개수로 설정하지 않고, 각 열의 크기를 2로 설정하지 않는 경우.

자주 묻는 질문3

Merge Intervals의 시간 복잡도는 얼마인가요?

정렬 및 스윕 솔루션은 n개의 구간에 대해 O(n log n) 시간에 실행됩니다. 정렬에는 O(n log n)이 걸리고 스윕에는 O(n)이 걸립니다. 정렬된 쌍과 결과를 위해 O(n)의 추가 공간을 사용합니다.

구간을 끝이 아니라 시작 기준으로 정렬하는 이유는 무엇인가요?

시작점 기준으로 정렬하면 구간은 현재 만들고 있는 그룹과만 겹칠 수 있으므로, 그 그룹의 끝점과 한 번 비교하면 모든 것이 결정됩니다. 끝점 기준으로 정렬하면 나중 구간의 시작점이 이미 닫은 그룹보다 앞설 수 있습니다. [5, 6]이 [1, 10]보다 먼저 오며, 앞에서부터 순회하면 시작점으로 5를 잘못 유지하게 됩니다.

추가 공간 없이 구간을 병합할 수 있나요?

네, 입력을 변경해도 된다면 가능합니다. 구간을 제자리에서 정렬한 다음, 병합된 각 구간을 같은 배열의 앞쪽에 덮어 쓰고 마지막으로 쓴 구간의 인덱스를 유지하세요. 시간 복잡도는 O(n log n)으로 유지되며, 추가 공간은 사용하는 언어의 정렬 기능이 필요로 하는 공간뿐입니다.

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

테스트 #1

테스트 #2

인자들

starts = [5, 1, 12, 3]
ends = [7, 4, 14, 6]

예상 출력

[[1, 7], [12, 14]]