C++ 작업 스케줄링 문제: 겹치지 않는 작업으로 최대 이익 구하기

문제 개요

서로 다른 n개의 작업이 있다고 가정해 봅시다. 각 작업은 startTime[i]부터 endTime[i]까지 수행되며, 해당 작업을 완료하면 profit[i]만큼의 이익을 얻습니다. startTime, endTime, profit 배열이 주어졌을 때, 두 작업의 실행 시간이 서로 겹치지 않도록 작업 부분 집합을 구성해 얻을 수 있는 최대 이익을 구하는 것이 이 문제의 목표입니다. 단, 한 작업이 시간 X에 종료된다면 시간 X에 시작하는 다른 작업을 바로 수행할 수 있다는 점에 유의하세요.

입력 예시

예를 들어 입력이 다음과 같다고 가정해 보겠습니다.

startTime = [1,2,3,3]
endTime = [3,4,5,6]
profit = [500,100,400,700]

이때 출력 결과는 1200입니다. 첫 번째 작업(1~3, 수익 500)과 네 번째 작업(3~6, 수익 700)을 선택하면 실행 시간이 겹치지 않으면서 총 수익 1200을 달성할 수 있기 때문입니다.

풀이 접근 방법

이 문제는 동적 계획법(DP)과 이분 탐색(Binary Search)을 결합하면 효율적으로 해결할 수 있습니다. 전체 알고리즘 흐름은 다음과 같습니다.

시작 시간(s), 종료 시간(e), 수익(c)을 저장하는 Data 구조체를 정의합니다.
Data 객체를 담을 배열 j를 만들고, 각 작업 정보를 하나씩 삽입합니다(n은 s의 크기).
배열 j를 종료 시간 기준으로 오름차순 정렬합니다.
크기가 n인 DP 배열 dp를 선언하고 dp[0] := j[0].cost로 초기화합니다.
i := 1부터 i < n까지 반복하면서 다음 과정을 수행합니다.
- low := 0, high := i - 1로 설정한 뒤, low < high인 동안 이분 탐색을 진행합니다.
  - mid := low + (high - low + 1) / 2
  - j[mid].end <= j[i].start이면 low := mid, 그렇지 않으면 high := mid - 1
- 탐색이 끝나면 dp[i] := j[i].cost로 초기화합니다.
- 만약 j[low].end <= j[i].start라면, 현재 작업과 겹치지 않으면서 가장 늦게 끝나는 이전 작업을 찾은 것이므로 dp[i] := dp[i] + dp[low]
- 마지막으로 dp[i] := max(dp[i], dp[i - 1])로 갱신하여 현재 작업을 건너뛰는 경우도 함께 고려합니다.
최종적으로 dp[n - 1]을 반환합니다.

핵심 아이디어는 각 작업마다 '현재 작업을 선택했을 때의 최대 이익'과 '현재 작업을 건너뛰었을 때의 최대 이익' 중 더 큰 값을 DP 테이블에 누적하는 것입니다. 이분 탐색 덕분에 각 작업마다 겹치지 않는 직전 작업을 O(log n)에 찾을 수 있으므로, 전체 시간 복잡도는 정렬을 포함해 O(n log n)이 됩니다.

C++ 구현 예제

아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
struct Data{
   int s,e,c;
   Data(int x, int y, int z){
      s= x;
      e= y;
      c = z;
   }
};
bool cmp(Data a, Data b){
   return a.e<b.e;
}
class Solution {
   public:
   int jobScheduling(vector<int>& s, vector<int>& e, vector<int>& p){
      vector<Data> j;
      int n = s.size();
      for (int i = 0; i < n; i++) {
         Data temp(s[i], e[i], p[i]);
         j.push_back(temp);
      }
      sort(j.begin(), j.end(), cmp);
      vector<int> dp(n);
      dp[0] = j[0].c;
      for (int i = 1; i < n; i++) {
         int temp = 0;
         int low = 0;
         int high = i - 1;
         while (low < high) {
            int mid = low + (high - low + 1) / 2;
            if (j[mid].e <= j[i].s)
               low = mid;
            else
               high = mid - 1;
         }
         dp[i] = j[i].c;
         if (j[low].e <= j[i].s)
            dp[i] += dp[low];
         dp[i] = max(dp[i], dp[i - 1]);
      }
      return dp[n - 1];
   }
};
main(){
   Solution ob;
   vector<int> startTime = {1,2,3,3}, endTime = {3,4,5,6}, profit =
   {500,100,400,700};
   cout << (ob.jobScheduling(startTime, endTime, profit));
}

실행 결과

입력:

{1,2,3,3}, {3,4,5,6}, {500,100,400,700}

출력: