C++로 풀어보는 겹치지 않는 두 구간의 최소 크기 합 구하기

[시작, 끝] 시간 정보를 담고 있는 구간(interval) 목록이 주어졌다고 가정해 보겠습니다. 우리의 목표는 서로 겹치지 않는 두 구간을 골라 그 크기의 합이 최소가 되도록 하는 것입니다. 여기서 구간의 크기는 (끝 - 시작 + 1)로 정의되며, 조건을 만족하는 두 구간을 찾을 수 없다면 0을 반환해야 합니다.

문제 예시

예를 들어 입력이 [[2,5],[9,10],[4,6]]라고 해보겠습니다. 이 경우 출력은 5가 됩니다. 크기가 3인 구간 [4,6]과 크기가 2인 구간 [9,10]을 선택하면 두 구간은 서로 겹치지 않으면서 크기의 합이 3 + 2 = 5로 최소가 되기 때문입니다.

접근 방법

이 문제는 정렬 + 이진 탐색 + 동적 계획법(DP)을 결합하여 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 구간들을 끝 시간(end) 기준으로 오름차순 정렬합니다.
• dp[i]에는 0번부터 i번 구간까지 고려했을 때 선택 가능한 구간의 최소 크기를 저장합니다.
• 각 구간 i에 대해, 현재 구간의 시작 시간보다 끝나는 시점이 앞선(즉, 겹치지 않는) 구간들 중 최소 크기를 이진 탐색으로 빠르게 찾습니다.
• 찾은 값(temp)과 현재 구간의 크기(val)를 더해 정답(ret)을 갱신합니다.

알고리즘 단계

1. ret := 무한대(inf)로 초기화하고, n := v의 크기로 설정합니다.
2. 배열 v를 끝 시간 기준으로 정렬합니다.
3. 크기가 n인 배열 dp를 선언합니다.
4. i를 0부터 v의 크기 - 1까지 반복하며 다음을 수행합니다.
   • low := 0, high := i - 1, temp := inf로 초기화합니다.
   • val := v[i][1] - v[i][0] + 1 (현재 구간의 크기)
   • low <= high 동안 이진 탐색을 수행합니다.
     • mid := low + (high - low) / 2
     • v[mid][1] >= v[i][0]이면(두 구간이 겹치면) high := mid - 1
     • 그렇지 않으면 temp := min(temp, dp[mid])로 갱신한 뒤 low := mid + 1
   • temp가 inf가 아니라면 ret := min(ret, temp + val), dp[i] := min(val, temp)
   • 그렇지 않으면 dp[i] := val
   • i > 0이면 dp[i] := min(dp[i], dp[i-1])로 누적 최솟값을 유지합니다.
5. ret이 여전히 inf라면 0을, 그렇지 않으면 ret을 반환합니다.

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 solve(vector<vector<int>>& v) {
      int ret = INT_MAX;
      int n = v.size();
      sort(v.begin(), v.end(), cmp);
      vector <int> dp(n);
      for(int i = 0; i < v.size(); i++){
         int low = 0;
         int high = i - 1;
         int temp = INT_MAX;
         int val = v[i][1] - v[i][0] + 1;
         while(low <= high){
            int mid = low + (high - low) / 2;
            if(v[mid][1] >= v[i][0]){
               high = mid - 1;
            }else{
               temp = min(temp, dp[mid]);
               low = mid + 1;
            }
         }
         if(temp != INT_MAX){
            ret = min(ret, temp + val);
            dp[i] = min(val, temp);
         }else{
            dp[i] = val;
         }
         if(i > 0) dp[i] = min(dp[i], dp[i - 1]);
      }
      return ret == INT_MAX ? 0 : ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{2,5},{9,10},{4,6}};
   cout << (ob.solve(v));
}

실행 결과

입력:

{{2,5},{9,10},{4,6}}

출력:

5

복잡도 분석

구간을 정렬하는 데 O(n log n)이 걸리고, 각 구간마다 한 번씩 이진 탐색을 수행하므로 전체 시간 복잡도는 O(n log n)입니다. 공간 복잡도는 DP 배열 사용으로 인해 O(n)입니다. 단순 이중 반복문으로 모든 구간 쌍을 비교하는 O(n²) 방식보다 훨씬 효율적이므로, 입력 크기가 큰 문제에서도 안정적인 성능을 기대할 수 있습니다.