문제 설명
임의의 순서로 나열된 시간 구간(intervals) 집합이 주어졌을 때, 서로 겹치는 모든 구간을 하나로 합쳐서 결과에 상호 배타적인 구간만 남도록 만드는 것이 이 문제의 목표입니다.
예를 들어 주어진 구간 집합이 {{12, 14}, {11, 13}, {20, 22}, {21, 23}}이라면 다음과 같이 병합됩니다.
{12, 14}와 {11, 13}은 서로 겹치기 때문에 하나로 합쳐 {11, 14}가 됩니다.
{20, 22}와 {21, 23} 역시 서로 겹치기 때문에 {20, 23}으로 병합됩니다.
알고리즘
스택(stack) 자료구조를 활용하면 이 문제를 깔끔하게 해결할 수 있습니다. 두 구간이 겹치는 조건은 “현재 구간의 시작 시간이 스택 최상단 구간의 종료 시간보다 작거나 같은 경우”입니다. 전체 절차는 다음과 같습니다.
- 시작 시간을 기준으로 모든 구간을 오름차순으로 정렬합니다.
- 첫 번째 구간을 스택에 넣습니다(push).
- 나머지 각 구간에 대해 아래 작업을 반복합니다.
3-1. 현재 구간이 스택 최상단(top) 구간과 겹치지 않으면 그대로 스택에 넣습니다.
3-2. 현재 구간이 최상단 구간과 겹치면서 종료 시간이 더 길다면, 최상단 구간의 종료 시간을 현재 구간의 종료 시간으로 갱신합니다. - 모든 처리가 끝나면 스택에는 병합된 구간들만 남아 있습니다.
시간 복잡도
정렬 단계가 전체 성능을 좌우하므로 시간 복잡도는 O(n log n)이며, 스택에 구간을 저장하므로 공간 복잡도는 O(n)입니다.
C++ 구현 예제
#include <iostream>
#include <algorithm>
#include <stack>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
struct interval{
int start;
int end;
};
bool compareInterval(interval i1, interval i2){
return (i1.start < i2.start);
}
void mergeOverlappingIntervals(interval *arr, int n){
if (n <= 0) {
return;
}
stack<interval> s;
sort(arr, arr + n, compareInterval);
s.push(arr[0]);
for (int i = 1; i < n; ++i) {
interval top = s.top();
if (top.end < arr[i].start) {
s.push(arr[i]);
} else if(top.end < arr[i].end) {
top.end = arr[i].end;
s.pop();
s.push(top);
}
}
cout << "Merged intervals: " << endl;
while (!s.empty()) {
interval i = s.top();
cout << "{" << i.start << ", " << i.end << "}" << " ";
s.pop();
}
cout << endl;
}
int main(){
interval arr[] = {{12, 14}, {11, 13}, {20, 22}, {21, 23}};
mergeOverlappingIntervals(arr, SIZE(arr));
return 0;
}실행 결과
위 프로그램을 컴파일하여 실행하면 다음과 같은 출력이 생성됩니다.
Merged intervals:
{20, 23} {11, 14}스택은 LIFO(후입선출) 구조이기 때문에, 출력 시 시작 시간이 늦은 구간({20, 23})이 먼저 표시되고 시작 시간이 빠른 구간({11, 14})이 나중에 표시됩니다. 결과의 순서가 중요하다면 병합된 구간들을 벡터 등에 옮겨 담은 뒤 정렬하여 출력하면 됩니다.