Non-overlapping Intervals
구간 i는 starts[i]부터 ends[i]까지입니다. 나머지 구간 중 서로 겹치는 구간이 없도록 제거해야 하는 구간의 최소 개수를 반환하세요. 한 구간이 끝나는 지점에서 다른 구간이 시작되어 맞닿기만 하는 두 구간은 겹치지 않습니다.
함수
- 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입니다.
후속 질문
모든 구간에 값이 있고 서로 겹치지 않는 구간들 중 총값이 가장 큰 경우를 찾고 싶다고 가정해 봅시다. 가장 먼저 끝나는 구간을 계속 선택하는 방법이 여전히 통할까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
무엇을 제거할지 선택하는 대신, 무엇을 남길지 생각해 보세요. 남길 수 있는 가장 큰 구간 집합은 답과 어떤 관련이 있을까요?
모든 구간 중 가장 먼저 끝나는 구간이 나머지 구간을 위한 공간을 가장 많이 남깁니다. 최적의 해답에는 언제나 이 구간이 포함됩니다.
구간을 끝나는 지점 기준으로 정렬한 다음, 마지막으로 남긴 구간의 끝을 기억하면서 순회하세요. 시작 지점이 그 끝과 같거나 그 이후인 구간은 남기고, 나머지 구간은 제거된 것으로 계산합니다.
풀이
가장 적은 수의 구간을 제거하는 것은 겹치지 않는 구간을 가장 많이 남기는 것과 같습니다. 답은 n에서 그 개수를 뺀 값입니다. O(n log n)으로 개수를 찾는 탐욕적 규칙은 다음과 같습니다. 아직 들어맞는 구간 중에서 항상 가장 먼저 끝나는 구간을 남깁니다.
각 구간을 유지하거나 제거하기
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
구간을 시작점 기준으로 정렬하고, 각 구간을 유지할지 제거할지 결정하세요. 마지막으로 유지한 구간의 끝점과 같거나 그 이후에 시작하는 경우에만 유지할 수 있으므로, 유지된 구간은 서로 겹치지 않는 하나의 연결된 순서를 이룹니다. 각 구간에서 두 가지 선택을 모두 시도하고 더 큰 개수를 선택하세요. 정답은 n에서 그 값을 뺀 것입니다.
각 구간은 분기 수를 두 배로 늘릴 수 있으므로, n개의 구간은 최대 2^n개의 경로로 이어집니다. 겹치지 않는 구간 30개만으로도 이미 10억 번이 넘는 호출이 필요하며, n은 최대 5000입니다.
알고리즘
- 각 시작점을 해당 끝점과 함께 유지하면서 구간을 시작점 기준으로 정렬합니다.
mostKept(i, 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] 이하이므로, 시작 시각이 더 이르고 정렬 순서에서도 앞에 온다. 따라서 가능한 j 중 가장 좋은 값에 대해 chain[i] = 1 + chain[j]가 되고, 들어맞는 구간이 없으면 1이다. 첫 번째 예에서 값은 1, 1, 2, 2이므로 2개를 유지하고 2개를 제거한다.
이중 반복문은 n(n-1)/2번 확인한다. n = 5000일 때 약 1,250만 번이다.
알고리즘
- 각 시작점과 해당 끝점을 함께 유지하면서 구간을 시작점 기준으로 정렬합니다.
- 모든 구간에 대해
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)그리디: 가장 먼저 끝나는 구간을 선택하세요
핵심 아이디어
끝점이 가장 작은 구간을 선택합니다. 최적의 답 중 하나는 이 구간을 포함합니다. 가장 큰 집합에서 가장 먼저 선택되는 구간을 이 구간으로 바꿔도 됩니다. 이 구간은 끝나는 시점이 더 늦지 않으므로, 여전히 다음에 선택되는 구간이 시작되는 시점 이전이나 그 시점에 끝나며, 집합의 크기는 그대로이고 겹치는 구간도 없습니다. 끝점보다 먼저 시작하는 모든 구간은 이 구간과 겹치므로 제거해야 합니다. 남은 구간에 대해서는 끝점과 같거나 그 이후에 시작하는 구간만 고려하는 동일한 문제가 됩니다.
첫 번째 예제에서는 끝점을 기준으로 정렬한 뒤 [2,3]을 선택하고 [1,4]를 제거하며, [3,6]을 선택하고 [5,7]을 제거합니다. 대신 가장 짧은 구간을 선택하면 [1,5], [4,7], [6,10]에서 실패합니다. [4,7]은 나머지 두 구간과 모두 겹치므로, 한 번이면 충분한 제거를 두 번 해야 합니다.
정렬에는 O(n log 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]의 연쇄에서 0이 아니라 1이 나옵니다. - 시작점을 기준으로 정렬한 뒤 겹치는 구간 중 앞선 구간을 남기는 경우. 너비가 넓은 [0,100]이 [1,2], [3,4], [5,6]을 밀어내므로 제거 횟수가 1이 아니라 3이 됩니다.
- 정렬된 목록에서 마지막으로 남긴 구간이 아니라 각 구간을 이웃 구간과 비교하는 경우. 첫 번째 예시에서 [3,6]은 제거된 [1,4]의 끝점이 아니라 [2,3]의 끝점과 비교해야 합니다. 그렇지 않으면 답이 3이 됩니다.
starts와ends를 별개의 목록으로 정렬하는 경우. 각 끝점은 자신의 시작점과 함께 있어야 합니다.- 제거한 구간의 개수가 아니라 남긴 구간의 개수를 반환하는 경우.
자주 묻는 질문3
겹치지 않는 구간의 시간 복잡도는 얼마인가요?
그리디 해법은 끝나는 시점을 기준으로 O(n log n)에 정렬하고 구간을 한 번 순회하므로, 정렬된 복사본을 위한 O(n)의 공간을 사용하며 전체 시간 복잡도는 O(n log n)입니다. 동적 계획법 버전은 O(n²)이고, 유지할 모든 집합을 시도하는 방법은 O(2^n)입니다.
대신 시작 시간순으로 정렬할 수 있나요?
네, 겹치는 경우에 다른 규칙을 적용하면 됩니다. 시작점을 기준으로 구간을 살펴보고, 다음 구간이 마지막으로 유지한 구간과 겹치면 제거 횟수를 1 늘린 다음 두 구간 중 더 먼저 끝나는 구간을 유지하세요. 같은 개수를 구하며 시간 복잡도도 O(n log n)으로 동일합니다.
겹치지 않는 구간 문제는 활동 선택 문제와 같은가요?
이는 그 문제의 반대 측면입니다. 활동 선택 문제는 겹치지 않는 구간을 최대한 많이 고르는 것을 묻지만, 이 문제는 제거해야 하는 구간을 최소화하는 것을 묻습니다. 그 수는 n에서 해당 구간의 수를 뺀 값입니다. 가장 먼저 끝나는 활동을 남긴다는 동일한 그리디 규칙으로 두 문제를 모두 해결할 수 있습니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def eraseOverlapIntervals(starts, ends):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자들
starts = [3, 1, 5, 2] ends = [6, 4, 7, 3]
예상 출력
2