Algorithms/Greedy

2.12.2 Interval Merging

개념

구간 병합은 여러 구간이 덮는 범위를 겹치지 않는 구간들로 정리하는 방법입니다. 예약된 시간이나 사용 중인 번호 범위를 합칠 때 사용합니다. 구간 선택은 일부 구간을 골라 개수를 최대화하지만, 병합은 모든 구간이 덮는 범위를 보존합니다.

시작점 순서로 확인

시작점이 작은 순서로 정렬하고, 현재 합치고 있는 구간의 양 끝점을 ll, rr로 저장합니다. 다음 구간을 [s,e][s,e]라고 하면 두 경우로 나뉩니다.

조건처리
s≤rs\le r겹치거나 끝점이 닿으므로 rr을 max⁡(r,e)\max(r,e)로 갱신
r<sr<s현재 구간을 결과에 넣고 [s,e][s,e]를 새 구간으로 시작

예를 들어 정렬한 구간이 [1,4][1,4], [2,3][2,3], [4,6][4,6], [8,9][8,9]이면 먼저 [1,4][1,4]를 저장합니다. [2,3][2,3]은 그 안에 포함되므로 오른쪽 끝점은 44입니다. [4,6][4,6]은 끝점이 닿으므로 [1,6][1,6]으로 합칩니다. [8,9][8,9]는 떨어져 있으므로 최종 결과는 [1,6][1,6], [8,9][8,9]입니다.

떨어진 구간을 확정하는 이유

현재 오른쪽 끝점이 rr이고 다음 시작점 ss가 rr보다 크다면, 뒤의 구간들도 시작점이 ss 이상입니다. 시작점 순서로 정렬했기 때문입니다. 따라서 뒤의 어떤 구간도 현재 구간과 겹칠 수 없으므로 현재 구간을 확정할 수 있습니다.

합칠 때는 오른쪽 끝점을 두 끝점의 최댓값으로 정해야 합니다. 현재 구간 안에 들어가는 짧은 구간을 만났을 때 끝점을 줄이면 이미 덮고 있던 범위가 사라집니다.

복잡도

구간 수를 NN이라고 합니다.

연산시간복잡도공간복잡도
정렬을 포함한 병합O(Nlog⁡N)O(N\log N)입력·결과 저장 O(N)O(N)
정렬된 구간 확인O(N)O(N)결과 저장 O(N)O(N)

예제

문제

주어진 구간들 중 겹치거나 끝점이 닿는 구간을 모두 합쳐라.

입력

첫째 줄에 구간 수 NN이 주어진다. 1≤N≤1001\le N\le100이다.

다음 NN개 줄에 구간의 시작점 ss와 끝점 ee가 공백을 사이에 두고 주어진다. 1≤s<e≤1 0001\le s<e\le1\,000이다.

출력

첫째 줄에 병합된 구간 수를 출력한다. 다음 줄부터 각 구간의 시작점과 끝점을 공백을 사이에 두고 한 줄에 출력한다. 구간은 시작점이 작은 순서대로 출력한다.

예제 입력

4
1 4
2 3
4 6
8 9

예제 출력

2
1 6
8 9

예제 코드

C++20

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;

bool compare(const pair<int, int>& a, const pair<int, int>& b) {
    // 시작점 오름차순, 시작점이 같으면 끝점 오름차순
    if (a.first != b.first) return a.first < b.first;
    return a.second < b.second;
}

vector<pair<int, int>> v, ans;

int main() {
    int n, i;

    cin >> n;
    v.resize(n);
    for (i = 0; i < n; ++i) {
        cin >> v[i].first >> v[i].second;
    }

    // 시작점 순서로 정렬 후 병합
    sort(v.begin(), v.end(), compare);
    for (const auto& [s, e] : v) {
        if (ans.empty() || ans.back().second < s) ans.push_back({s, e});
        else ans.back().second = max(ans.back().second, e);
    }

    cout << ans.size() << '\n';
    for (const auto& [s, e] : ans) {
        cout << s << ' ' << e << '\n';
    }
}