C++로 N개의 구간 전체의 교집합 찾기

문제 개요

N개의 구간 {L, R}이 주어졌다고 가정해 봅시다. 여기서 L은 시작 시점, R은 종료 시점을 의미합니다. 이때 우리가 구해야 할 것은 모든 구간에 공통으로 포함되는 교집합입니다. 만약 그러한 구간이 존재하지 않는다면 -1을 반환해야 합니다.

예를 들어, 구간이 [{1, 6}, {2, 8}, {3, 10}, {5, 8}]과 같이 주어진 경우, 네 구간 모두에 속하는 구간은 {5, 6}이므로 출력 결과는 {5, 6}이 됩니다.

접근 방법

이 문제는 다음 단계를 따라 해결할 수 있습니다.

• 첫 번째 구간을 일단 최종 교집합으로 간주합니다.
• 두 번째 구간부터 차례대로 순회하며 교집합 여부를 확인합니다. 이때 두 구간 [L1, R1]과 [L2, R2] 사이에는 두 가지 경우가 존재합니다.
  • 교집합이 존재하지 않는 경우: R1 < L2 또는 R2 < L1일 때만 발생하며, 이 경우 정답은 -1입니다.
  • 교집합이 존재하는 경우: 요구되는 교집합은 {max(L1, L2), min(R1, R2)}가 됩니다.

예제 코드

#include<iostream>
#include<algorithm>
using namespace std;
class interval{
    public:
        int left, right;
};
void findIntersection(interval intervals[], int N) {
    int l = intervals[0].left;
    int r = intervals[0].right;
    for (int i = 1; i < N; i++) {
        if (intervals[i].left > r || intervals[i].right < l) {
            cout << -1;
            return;
        } else {
            l = max(l, intervals[i].left);
            r = min(r, intervals[i].right);
        }
    }
    cout << "{" << l << ", " << r << "}";
}
int main() {
    interval intervals[] = {{ 1, 6 }, { 2, 8 }, { 3, 10 }, { 5, 8 } };
    int N = sizeof(intervals) / sizeof(intervals[0]);
    findIntersection(intervals, N);
}

실행 결과

{5, 6}

동작 원리 정리

위 알고리즘의 핵심 아이디어는 다음과 같습니다.

• 교집합의 시작점은 항상 각 구간 시작점 중 최댓값이 됩니다.
• 교집합의 끝점은 항상 각 구간 끝점 중 최솟값이 됩니다.
• 순회 도중 시작점의 최댓값이 끝점의 최솟값보다 커지면, 더 이상 공통 구간이 존재하지 않으므로 즉시 -1을 출력하고 종료합니다.

이 방식은 각 구간을 한 번씩만 확인하면 되므로 시간 복잡도는 O(N)이며, 추가 메모리 사용 없이 효율적으로 문제를 해결할 수 있습니다.