C++로 해결하는 겹치지 않는 간격 문제: 제거해야 할 최소 간격 개수 구하기

여러 개의 간격(interval)이 주어졌을 때, 나머지 간격들이 서로 겹치지 않도록 만들기 위해 제거해야 하는 간격의 최소 개수를 구하는 문제입니다.

예를 들어 간격이 [[1,2], [2,3], [3,4], [1,3]]과 같이 주어진 경우, [1,3]만 제거하면 나머지 간격들이 모두 겹치지 않게 되므로 출력값은 1이 됩니다.

문제 해결 전략

이 문제는 탐욕(Greedy) 알고리즘을 활용해 효율적으로 해결할 수 있습니다. 핵심 아이디어는 간격을 끝나는 시점(end) 기준으로 정렬한 뒤, 겹치지 않고 선택할 수 있는 간격의 수를 최대화하는 것입니다. 선택되는 간격이 많아질수록 제거해야 할 간격은 자연히 줄어들기 때문입니다.

구체적인 단계는 다음과 같습니다.

n := 배열의 크기
n이 0이면 0을 반환합니다.
count := 1 (첫 번째 간격은 항상 선택)
간격들을 끝나는 시간(end) 기준으로 오름차순 정렬합니다.
end := 첫 번째 간격의 끝나는 시간
i를 1부터 n-1까지 반복합니다.
- arr[i]의 시작 시간이 end보다 크거나 같으면:
  - end := arr[i]의 끝나는 시간으로 갱신
  - count를 1 증가
최종적으로 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 = {{1,2},{1,2},{1,2}};
   Solution ob;
   cout << (ob.eraseOverlapIntervals(v));
}

입력

[[1,2],[1,2],[1,2]]

출력

동작 원리와 복잡도

위 예제에서 세 개의 간격 [1,2]가 모두 완전히 겹치므로, 하나만 남기고 나머지 두 개를 제거해야 합니다. 따라서 결과는 2가 됩니다.

끝나는 시간 기준으로 정렬하면, 가능한 한 빨리 끝나는 간격부터 선택하게 되어 이후 간격들과 겹칠 확률을 최소화할 수 있습니다. 이것이 탐욕적 선택이 최적해를 보장하는 이유입니다.

정렬에 O(n log n), 순회에 O(n)이 소요되므로 전체 시간 복잡도는 O(n log n)이며, 추가 공간 없이 제자리(in-place) 정렬을 사용하기 때문에 공간 복잡도는 O(1)입니다.