여러 개의 구간(interval)이 주어졌을 때, 남은 구간들이 서로 겹치지 않도록 만들기 위해 최소 몇 개의 구간을 제거해야 하는지 구하는 문제입니다. 예를 들어 구간이 [[8,10],[3,5],[6,9]]라면, [6,9] 하나만 제거하면 나머지 구간이 모두 겹치지 않으므로 정답은 1이 됩니다.
문제 해결 접근 방식
이 문제는 그리디(Greedy) 알고리즘으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 끝나는 시간이 빠른 구간부터 선택하는 것입니다. 구간이 일찍 끝날수록 뒤에 오는 구간과 겹칠 가능성이 줄어들어, 더 많은 구간을 유지할 수 있기 때문입니다.
알고리즘의 단계는 다음과 같습니다.
- n := 배열의 크기
- n이 0이면 0을 반환
- count := 1로 초기화
- 구간의 끝나는 시간을 기준으로 배열 정렬
- end := 첫 번째 구간의 끝나는 시간
- i를 1부터 n-1까지 반복:
- arr[i]의 시작 시간이 end보다 크거나 같으면(겹치지 않으면):
- end := arr[i]의 끝나는 시간으로 갱신
- count 1 증가
- arr[i]의 시작 시간이 end보다 크거나 같으면(겹치지 않으면):
- n - count 반환 (제거해야 할 구간의 수)
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
static bool cmp(vector<int>& a, vector<int>& b){
return a[1] < b[1];
}
int eraseOverlapIntervals(vector<vector<int>>& arr) {
int n = arr.size();
if(!n) return 0;
int cnt = 1;
sort(arr.begin(), arr.end(), cmp);
int end = arr[0][1];
for(int i = 1; i < n; i++){
if(arr[i][0] >= end){
end = arr[i][1];
cnt++;
}
}
return n - cnt;
}
};
main(){
vector<vector<int>> v = {{8,10},{3,5},{6,9}};
Solution ob;
cout << (ob.eraseOverlapIntervals(v));
}입력
{{8,10},{3,5},{6,9}}출력
1
동작 원리 살펴보기
예제의 구간들을 끝나는 시간 기준으로 정렬하면 [3,5], [6,9], [8,10] 순서가 됩니다. 먼저 첫 번째 구간 [3,5]를 선택하고 end를 5로 설정합니다. 다음 구간 [6,9]의 시작 시간 6은 5보다 크므로 겹치지 않으며, end를 9로 갱신합니다. 마지막 구간 [8,10]의 시작 시간 8은 9보다 작으므로 앞 구간과 겹치게 되고, 이 구간이 제거 대상이 됩니다. 따라서 전체 3개 중 2개를 유지하고 1개만 제거하면 되므로 결과는 1입니다.
정렬에 O(n log n), 이후 순회에 O(n)이 소요되므로 이 알고리즘의 전체 시간 복잡도는 O(n log n)입니다.