문제 설명
이 문제에서는 N개의 구간(interval)이 주어졌을 때, 서로 겹치지 않는 구간들의 최대 집합을 찾아야 합니다. 두 구간 [i, j]와 [k, l]은 공통으로 포함되는 점이 하나도 없을 때 '서로소(disjoint)' 관계에 있다고 정의합니다.
예를 들어 구간이 {{10, 20}, {23, 35}, {15, 21}, {37, 41}}처럼 주어진 경우, 서로 겹치지 않는 최대 구간 집합은 다음과 같습니다.
{10, 20}
{23, 35}
{37, 41}{15, 21}은 {10, 20}과 겹치기 때문에 결과 집합에는 포함될 수 없습니다.
해결 알고리즘
이 문제는 대표적인 그리디(Greedy) 알고리즘으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 주어진 구간들을 끝점(end point)을 기준으로 오름차순 정렬합니다.
- 정렬된 구간을 순서대로 순회하면서, 직전에 선택한 구간의 끝점보다 시작점이 큰(즉, 겹치지 않는) 구간만 선택합니다. 끝점이 작은 구간을 우선 선택하면 이후 등장하는 구간들과 겹칠 가능성을 최소화할 수 있어 더 많은 구간을 담을 수 있습니다.
- 위 과정을 모든 구간에 대해 반복하고, 조건을 만족하는 구간들을 출력합니다.
정렬에 O(N log N), 순회에 O(N)의 시간이 소요되므로 전체 시간 복잡도는 O(N log N)입니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
bool sortFun(pair<int, int> &a, pair<int, int> &b){
return (a.second < b.second);
}
void getMaxDisjointInterval(vector<pair<int, int>> intervals){
sort(intervals.begin(), intervals.end(), sortFun);
cout << "{" << intervals[0].first << ", " << intervals[0].second << "}\n";
int r1 = intervals[0].second;
for (int i = 1; i < intervals.size(); ++i) {
int l1 = intervals[i].first;
int r2 = intervals[i].second;
if (l1 > r1) {
cout << "{" << l1 << ", " << r2 << "}\n";
r1 = r2;
}
}
}
int main(){
int n = 4;
vector<pair<int, int>> intervals = {
{10, 20},
{23, 35},
{15, 21},
{37, 41}
};
cout << "Max disjoint pairs are:\n";
getMaxDisjointInterval(intervals);
return 0;
}
실행 결과
위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.
Max disjoint pairs are:
{10, 20}
{23, 35}
{37, 41}
마무리
구간 스케줄링 문제로도 알려진 이 유형은 회의실 배정, 강의 시간표 최적화 등 실무에서 자주 응용됩니다. 핵심은 '끝점 기준 정렬'이라는 단순하지만 강력한 그리디 전략임을 기억하세요.