Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++에서 작업 스케줄링의 최대 이익

<시간/>

모든 작업이 startTime[i]에서 endTime[i]까지 수행되도록 예약된 n개의 다른 작업이 있다고 가정하고 해당 작업에 대해 이익[i]을 얻습니다. 우리는 startTime , endTime 및 이익 목록을 알고 있으므로 중첩되는 시간 범위를 가진 하위 집합에 2개의 작업이 없도록 최대 이익을 찾아야 합니다. X 시간에 끝나는 작업을 선택하면 X 시간에 시작하는 다른 작업을 시작할 수 있습니다.

따라서 입력이 startTime =[1,2,3,3]과 같으면 endTime =[3,4,5,6] 이익 =[500,100,400,700]

C++에서 작업 스케줄링의 최대 이익

그러면 출력은 1200이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

  • 시작, 종료 및 비용 값으로 하나의 데이터 정의
  • 데이터 j의 하나의 배열을 만듭니다.

  • n :=s

    의 크기
  • initialize i :=0의 경우, i

    • 하나의 데이터 temp(s[i], e[i], p[i])

      생성
    • j의 끝에 temp 삽입

  • 종료 시간을 기준으로 배열 j 정렬

  • 크기가 n

    인 배열 dp를 정의합니다.
  • dp[0] :=j[0].비용

  • initialize i :=1의 경우 i

    • 온도 :=0, 낮음 :=0, 높음 :=i - 1

    • 낮음 <높음, 수행 -

      • 중간 :=낮음 + (높음 - 낮음 + 1) / 2

      • j[mid].end <=j[i].start이면 -

        • 낮음 :=중간

      • 그렇지 않으면

        • 높음 :=중간 - 1

      • dp[i] :=j[i].비용

      • j[low].end <=j[i].start이면 -

        • dp[i] :=dp[i] + dp[낮음]

    • dp[i] :=dp[i] 및 dp[i - 1]

      의 최대값
  • 반환 dp[n - 1]

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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}

출력

1200