C++ এ কাজের সময়সূচীতে সর্বোচ্চ লাভ

ধরুন আমাদের বিভিন্ন টাস্ক আছে, যেখানে প্রতিটি কাজ স্টার্টটাইম[i] থেকে এন্ডটাইম[i] পর্যন্ত করার জন্য নির্ধারিত আছে, সেই কাজের জন্য আমরা লাভের লাভ [i] পাই। আমরা স্টার্টটাইম, এন্ডটাইম এবং লাভের তালিকা জানি, আমাদের সর্বোচ্চ মুনাফা খুঁজে বের করতে হবে যাতে ওভারল্যাপিং টাইম রেঞ্জ সহ সাবসেটে কোন 2টি কাজ না থাকে। আমরা যদি X সময়ে শেষ হয় এমন একটি কাজ বেছে নিলে আমরা X সময়ে শুরু হওয়া অন্য একটি কাজ শুরু করতে সক্ষম হব।

সুতরাং, যদি ইনপুট হয় startTime =[1,2,3,3], endTime =[3,4,5,6] লাভ =[500,100,400,700]

তাহলে আউটপুট হবে 1200

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• শুরু, শেষ এবং খরচ মান সহ একটি ডেটা সংজ্ঞায়িত করুন

• ডেটার একটি অ্যারে তৈরি করুন j

• n :=s

  এর আকার

• আরম্ভ করার জন্য i :=0, যখন i

  • একটি ডেটা টেম্প(s[i], e[i], p[i])

    তৈরি করুন

  • j

    এর শেষে তাপমাত্রা সন্নিবেশ করুন

• শেষ সময়ের উপর ভিত্তি করে অ্যারে j সাজান

• n

  আকারের একটি অ্যারে ডিপি সংজ্ঞায়িত করুন

• dp[0] :=j[0]. খরচ

• আরম্ভ করার জন্য i :=1, যখন i

  • তাপমাত্রা :=0, কম :=0, উচ্চ :=i - 1

  • যখন কম <উচ্চ, করুন −

    • মধ্য :=নিম্ন + (উচ্চ - নিম্ন + 1) / 2

    • যদি j[মিড].এন্ড <=j[i].start হয়, তাহলে −

      • নিম্ন :=মধ্য

    • অন্যথায়

      • উচ্চ :=মধ্য - 1

    • dp[i] :=j[i]. খরচ

    • যদি j[low].end <=j[i].start হয়, তাহলে −

      • dp[i] :=dp[i] + dp[low]

  • 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