Non-overlapping Intervals
구간 목록은 두 개의 배열로 주어집니다. 구간 i는 starts[i]부터 ends[i]까지입니다. 남은 구간 중 어떤 두 구간도 겹치지 않도록 가능한 한 적은 수의 구간을 제거하세요. 한 구간이 끝나는 지점에서 다른 구간이 시작되어 서로 맞닿기만 하는 경우에는 겹치는 것으로 보지 않습니다.
제거해야 하는 구간의 최소 개수를 반환하는 eraseOverlapIntervals라는 함수를 작성하세요.
함수
- startsinteger-array
- 각 구간의 시작
- endsinteger-array
- 각 구간의 끝, 시작과 같은 인덱스
- 반환값integer
- 나머지 구간이 겹치지 않도록 제거해야 하는 구간의 최소 개수
제약 조건
1 ≤ starts.length == ends.length ≤ 5000-5 × 104 ≤ starts[i] < ends[i] ≤ 5 × 104- 구간은 정렬되어 있지 않습니다. 두 구간은 동일할 수 있습니다.
예제
- 입력
- starts = [3, 1, 5, 2]ends = [6, 4, 7, 3]
- 출력
- 2
- 설명
- 시작 순서대로 구간은 [1,4], [2,3], [3,6], [5,7]입니다. 서로 맞닿기만 하는 [2,3]과 [3,6]은 남기고 나머지 2개는 제거합니다. 세 개를 남길 수는 없습니다. [1,4]는 [2,3]과 겹치고 [3,6]은 [5,7]과 겹치며, 네 구간 중 어떤 세 구간을 골라도 이 쌍 중 하나가 포함되기 때문입니다.
- 입력
- starts = [0, 0, 0]ends = [5, 5, 5]
- 출력
- 2
- 설명
- 세 구간은 모두 [0,5]이므로, 어떤 두 구간을 선택해도 서로 겹칩니다. 하나만 남길 수 있으므로 나머지
2개를 제거합니다.
- 입력
- starts = [4, 1, 2]ends = [6, 2, 4]
- 출력
- 0
- 설명
- [1,2], [2,4], [4,6]은 끝과 시작이 맞닿아 있고 겹치지 않으므로 아무것도 제거하지 않으며, 답은
0입니다.
제출 시 숨은 테스트 +17개
후속 질문
각 구간에 값도 있고, 서로 겹치지 않는 구간들의 값의 합을 최대로 만들고 싶다고 가정해 봅시다. 가장 먼저 끝나는 구간을 계속 선택하는 방법이 여전히 통할까요? 대신 어떤 방법을 사용하시겠어요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
무엇을 제거할지 선택하는 대신, 무엇을 남길지 생각해 보세요. 남길 수 있는 구간의 최대 집합은 정답과 어떤 관련이 있을까요?
모든 구간 중 가장 먼저 끝나는 구간이 나머지 구간을 위한 공간을 가장 많이 남깁니다. 최적의 답은 항상 그 구간을 포함합니다.
구간을 끝을 기준으로 정렬하고, 마지막으로 유지한 구간의 끝을 기억하며 순회하세요. 그 끝과 같거나 그 이후에 시작하는 구간은 유지하고, 나머지 모든 구간은 제거된 것으로 계산합니다.
풀이
가장 적은 수의 구간을 제거하는 것은 겹치지 않는 구간을 가장 많이 유지하는 것과 같으므로, 정답은 n에서 그 최대 집합의 크기를 뺀 값입니다. 유지할 모든 집합을 시도하는 방식은 지수 시간이 걸리고, 구간의 연쇄를 대상으로 동적 계획법을 적용하면 O(n²)으로 줄어듭니다. 다음 그리디 규칙을 사용하면 O(n log n)에 해결할 수 있습니다. 아직 겹치지 않게 선택할 수 있는 구간 중 가장 먼저 끝나는 구간을 항상 유지하세요.
각 구간을 유지하거나 제거하세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
문제를 거꾸로 생각해 보세요. 제거할 구간의 수를 최소화한다는 것은 겹치지 않는 구간을 최대한 많이 남기는 것이며, 정답은 n에서 그 수를 뺀 값입니다. 그러니 남길 수 있는 가장 큰 집합을 찾아보세요.
구간을 시작점 기준으로 정렬한 뒤, 각 구간을 순서대로 제거할지 남길지 결정하세요. 남기려는 구간의 시작점이 마지막으로 남긴 구간의 끝점과 같거나 그보다 클 때만 남길 수 있습니다. 이 조건 하나면 충분합니다. 남긴 구간들은 각각 앞선 구간의 끝점과 같거나 그 이후에 시작하는 연결된 사슬을 이루므로, 서로 겹치는 구간이 없습니다. 각 구간에서 두 가지 선택을 모두 시도하고 더 나은 결과를 선택하세요.
첫 번째 예시에서 정렬된 구간은 [1,4], [2,3], [3,6], [5,7]입니다. [1,4]를 남기면 4보다 앞서 시작하는 [2,3]과 [3,6]이 막히고, [5,7]을 남길 수 있어 총 2개를 남깁니다. [1,4]를 제거하고 [2,3]을 남긴 다음 [3,6]도 남겨도 역시 2개입니다. 어느 분기에서도 3개를 남길 수 없으므로 4-2 = 2개를 제거합니다.
각 구간에서 분기 수가 두 배로 늘어날 수 있으므로, n개의 구간은 최대 2^n개의 경로로 이어집니다. 겹치지 않는 구간이 30개만 있어도 이미 10억 번이 넘는 호출을 의미하며, 테스트는 최대 5000개의 구간까지 있습니다. 재귀의 깊이도 n단계에 이릅니다. 가장 큰 테스트에서는 호출이 5000단계까지 이어져 Python의 기본 제한인 1,000을 초과합니다.
알고리즘
- 각 시작점을 해당 끝점과 함께 유지하면서 구간을 시작점 기준으로 정렬합니다.
mostKept(i, last)를 정의합니다.last가 가장 최근에 유지한 구간의 위치일 때(last가 없으면-1), 위치i부터 유지할 수 있는 구간의 최댓값입니다.- 목록의 끝을 지나면
0을 반환합니다. 그렇지 않으면 구간i를 제거한 결과인mostKept(i+1, last)에서 시작합니다. - 구간
i가 구간last의 끝에서 시작하거나 그 이후에 시작한다면,1 + mostKept(i+1, i)도 시도하고 더 큰 결과를 유지합니다. n에서mostKept(0, -1)을 뺀 값을 반환합니다.
def eraseOverlapIntervals(starts, ends):
intervals = sorted(zip(starts, ends)) # by start time
n = len(intervals)
def most_kept(i, last):
# The most intervals you can keep among i..n-1, when interval last
# is the latest one kept so far (-1: nothing kept yet).
if i == n:
return 0
best = most_kept(i + 1, last) # remove interval i
if last == -1 or intervals[i][0] >= intervals[last][1]:
best = max(best, 1 + most_kept(i + 1, i)) # keep interval i
return best
return n - most_kept(0, -1)동적 프로그래밍을 이용한 최장 체인
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
위의 탐색은 같은 질문에 계속해서 답합니다. 이 구간에서 끝나는 가장 긴 체인은 무엇일까요? 그 답을 구간마다 한 번씩 저장하세요. 시작점 기준으로 정렬하고, chain[i]를 구간 i가 마지막으로 유지되는 구간일 때 유지할 수 있는 최대 구간 수라고 합시다.
i 바로 앞에 유지되는 구간은 starts[i]와 같거나 그보다 일찍 끝나야 합니다. 이러한 모든 구간은 정렬 순서에서 더 앞에 옵니다. 구간은 끝나기 전에 시작하므로, starts[i]보다 먼저 시작합니다. 따라서 ends[j] ≤ starts[i]를 만족하는 이전 j 중 최선의 경우 chain[i] = 1 + chain[j]이고, 조건에 맞는 구간이 없으면 1입니다. chain에서 가장 큰 값이 유지할 수 있는 최대 구간 수입니다.
첫 번째 예시를 [1,4], [2,3], [3,6], [5,7] 순으로 정렬하면 값은 1, 1, 2, 2입니다. [3,6]은 [2,3] 뒤에 올 수 있고, [5,7]은 [1,4] 또는 [2,3] 뒤에 올 수 있습니다. 가장 긴 체인의 길이는 2이므로 4-2 = 2개를 제거합니다.
각 구간은 그보다 앞에 있는 모든 구간을 살펴보므로, n(n-1)/2번 확인합니다. n = 5000이면 약 12.5 million번 확인합니다. 컴파일 언어에서는 괜찮지만, 가장 큰 테스트에서는 느린 언어로 실행하기엔 너무 느리고 아래의 그리디 알고리즘보다 훨씬 비효율적입니다.
알고리즘
- 각 시작점을 해당 끝점과 함께 유지하면서 구간을 시작점 기준으로 정렬합니다.
- 모든 구간에 대해
chain[i] = 1로 설정합니다. - 각
i와ends[j] ≤ starts[i]를 만족하는 각j < i에 대해, 더 큰 값이라면chain[i]를chain[j]+1로 설정합니다. chain에서 가장 큰 값을n에서 뺀 값을 반환합니다.
def eraseOverlapIntervals(starts, ends):
intervals = sorted(zip(starts, ends)) # by start time
n = len(intervals)
# chain[i]: the most intervals you can keep when interval i is the last one kept
chain = [1] * n
for i in range(n):
for j in range(i):
if intervals[j][1] <= intervals[i][0] and chain[j] + 1 > chain[i]:
chain[i] = chain[j] + 1
return n - max(chain)그리디: 가장 먼저 끝나는 구간을 유지하세요
핵심 아이디어
끝점이 가장 작은 구간을 살펴보세요. 최선의 답에는 항상 이 구간이 포함됩니다. 유지할 수 있는 구간으로 이루어진 가장 큰 집합을 하나 고른 다음, 그 집합에서 가장 먼저 시작하는 구간을 이 구간으로 바꿔 보세요. 새 구간은 바꾼 구간보다 늦지 않게 끝나므로, 다음으로 유지하는 구간의 시작점과 같거나 그보다 앞서 끝납니다. 집합에는 여전히 겹치는 구간이 없고 크기도 그대로이므로, 끝점이 가장 이른 구간을 유지해도 손해가 없습니다.
이 구간을 유지하고 나면 끝점보다 먼저 시작하는 모든 구간은 이 구간과 겹치므로 제거해야 합니다. 남은 구간에 대해서도 끝점과 같거나 그 이후에 시작하는 구간만 고려하면 같은 문제가 되므로, 같은 규칙을 다시 적용하면 됩니다. 실제로는 끝점을 기준으로 정렬하고 목록을 순회하면서 마지막으로 유지한 구간의 끝점인 lastEnd를 기억합니다. 시작점이 lastEnd와 같거나 그 이후인 구간은 유지하고, 나머지는 제거된 것으로 셉니다.
첫 번째 예제를 끝점을 기준으로 정렬하면 [2,3], [1,4], [3,6], [5,7]입니다. [2,3]을 유지하므로 lastEnd = 3입니다. [1,4]는 1에서 시작해 3보다 앞서므로 제거합니다. [3,6]은 3에서 시작해 3보다 앞서지 않으므로 유지하고, lastEnd = 6으로 갱신합니다. [5,7]은 5에서 시작해 6보다 앞서므로 제거합니다. 두 개를 제거했습니다.
다른 기준도 그럴듯해 보이지만 실패합니다. 시작점을 기준으로 정렬하면 [0,100]이 [1,2], [3,4], [5,6]을 포함할 때 [0,100]을 유지하게 되어 구간 하나가 아니라 세 개를 제거합니다. 가장 짧은 구간을 유지하는 방법은 [1,5], [4,7], [6,10]에서 실패합니다. 짧은 [4,7]은 나머지 두 구간 모두와 겹치므로, 이를 유지하면 충분히 하나만 제거해도 되는 상황에서 두 개를 제거해야 합니다. 끝점을 기준으로 삼아야 이후의 모든 구간을 위한 공간을 가장 많이 남길 수 있습니다.
정렬에는 O(n log n)이 걸리고, 순회에는 O(n)이 걸립니다. 정렬된 구간 복사본에는 O(n)의 공간이 필요합니다.
알고리즘
- 각 구간의 끝을 해당 시작점과 함께 유지하면서 끝점 기준으로 구간을 정렬합니다.
- 첫 번째 구간을 유지합니다.
lastEnd를 해당 구간의 끝점으로 설정하고removed를0으로 설정합니다. - 그다음 각 구간이
lastEnd이상에서 시작하면 해당 구간을 유지하고lastEnd를 해당 구간의 끝점으로 설정합니다. - 그렇지 않으면
removed에 1을 더합니다. removed를 반환합니다.
def eraseOverlapIntervals(starts, ends):
intervals = sorted(zip(ends, starts)) # by end time
removed = 0
last_end = intervals[0][0] # the interval that ends first is always kept
for end, start in intervals[1:]:
if start >= last_end:
last_end = end # it fits after the last kept interval: keep it
else:
removed += 1 # it overlaps the last kept interval: remove it
return removed
함정과 경계 사례
대부분의 오답은 정렬 기준이나 경계가 맞닿는 지점의 비교에서 비롯됩니다.
- 경계가 맞닿는 구간을 겹치는 것으로 처리하는 경우.
start ≥ lastEnd대신start > lastEnd를 사용하면 [1,2], [2,4], [4,6]의 연결에서 [1,2]가 끝나는 지점에서 정확히 시작하는 [2,4]가 제거되어, 정답이 0이 아니라 1이 됩니다. - 시작점 기준으로 정렬하고 겹치는 구간 중 앞선 구간을 항상 유지하는 경우. 길이가 긴 [0,100]은 [1,2], [3,4], [5,6]을 밀어냅니다. 시작점 기준으로 정렬했다면 겹치는 두 구간 중 끝나는 지점이 더 이른 구간을 유지하세요.
- 정렬된 목록에서 각 구간을 마지막으로 유지한 구간이 아니라 바로 다음 구간과 비교하는 경우. [1,4]를 제거한 뒤에는 다음 구간을 4가 아니라 [2,3]의 끝과 비교해야 합니다.
starts와ends를 서로 다른 목록으로 정렬하는 경우. 각 끝점은 해당 시작점과 함께 유지되어야 합니다. 그렇지 않으면 어떤 구간의 시작점을 다른 구간의 끝점과 비교하게 됩니다.- 유지하는 구간의 개수를 반환하는 경우. 문제에서 요구하는 것은 제거된 구간의 개수이며, 이는
n에서 유지한 구간의 개수를 뺀 값입니다.
자주 묻는 질문4
Non-overlapping Intervals의 시간 복잡도는 얼마인가요?
그리디 해법은 구간을 끝을 기준으로 O(n log n)에 정렬한 다음 한 번 순회하므로 O(n)이 걸립니다. 따라서 전체 시간 복잡도는 O(n log n)입니다. 정렬된 구간 사본에는 O(n)의 공간이 사용됩니다. 동적 프로그래밍 버전의 시간 복잡도는 O(n²)이며, 유지할 모든 집합을 시도하면 O(2^n)이 걸립니다.
왜 종료 시간을 기준으로 정렬하면 제거 횟수를 최소화할 수 있을까요?
가장 먼저 끝나는 구간은 겹침을 만들지 않으면서 최적해의 첫 번째 구간을 대체할 수 있습니다. 더 늦게 끝나지 않기 때문입니다. 따라서 어떤 최적해는 이 구간을 포함하며, 이 구간과 겹치는 모든 구간을 제거하고 나면 남은 것은 더 작은 집합에서 같은 문제입니다. 이 논리를 반복하면 모든 탐욕적 선택이 안전하다는 것을 알 수 있습니다.
대신 시작 시간을 기준으로 정렬할 수 있나요?
네, 겹치는 경우에 다른 규칙을 적용하면 됩니다. 시작점을 기준으로 구간을 순회하고, 다음 구간이 마지막으로 유지한 구간과 겹치면 하나를 제거한 것으로 세고 두 구간 중 먼저 끝나는 구간을 유지합니다. 끝점을 기준으로 정렬하는 방법과 같은 수의 구간을 제거하며, 실행 시간도 동일한 O(n log n)입니다.
겹치지 않는 구간 문제는 활동 선택 문제와 같은가요?
그것의 반대쪽입니다. 활동 선택 문제에서는 서로 겹치지 않는 구간을 최대한 많이 선택하라고 요구하지만, 이 문제에서는 제거해야 할 구간을 최소한으로 구하라고 요구하며, 그 수는 n에서 그 개수를 뺀 값입니다. 가장 먼저 끝나는 활동을 유지한다는 동일한 그리디 규칙으로 두 문제를 모두 해결할 수 있습니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def eraseOverlapIntervals(starts, ends):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
starts = [3, 1, 5, 2] ends = [6, 4, 7, 3]
기대값
2