C++-এ জব শিডিউলিং থেকে সর্বোচ্চ প্রফিট (Maximum Profit in Job Scheduling)

n সংখ্যক কাজ দেওয়া আছে, প্রতিটি কাজ startTime[i] থেকে endTime[i] পর্যন্ত চলে এবং এর প্রফিট profit[i]। দুটি কাজ ওভারল্যাপ করবে না এমনভাবে কাজ বেছে নিয়ে সর্বোচ্চ প্রফিট বের করতে হবে। একটা কাজ X সময়ে শেষ হলে আরেকটা কাজ X সময় থেকে শুরু করা যায়।

উদাহরণ

ইনপুট: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [500,100,400,700]

আউটপুট: 1200

সমাধানের ধাপসমূহ

কাজগুলো শেষ সময় (endTime) অনুযায়ী সর্ট করুন।
DP অ্যারে ব্যবহার করুন: dp[i] = প্রথম i কাজ থেকে সর্বোচ্চ প্রফিট।
প্রতিটি কাজ i এর জন্য, বাইনারি সার্চ করে সর্বশেষ নন-ওভারল্যাপিং কাজ j খুঁজুন।
dp[i] = max(dp[i-1], profit[i] + dp[j])।

প্রোগ্রাম উদাহরণ

#include <bits/stdc++.h>
using namespace std;

struct Job {
    int s, e, c;
    Job(int x, int y, int z) : s(x), e(y), c(z) {}
};

bool cmp(Job a, Job b) { return a.e < b.e; }

class Solution {
public:
    int jobScheduling(vector<int>& s, vector<int>& e, vector<int>& p) {
        vector<Job> jobs;
        int n = s.size();
        for (int i = 0; i < n; i++)
            jobs.emplace_back(s[i], e[i], p[i]);
        
        sort(jobs.begin(), jobs.end(), cmp);
        vector<int> dp(n);
        dp[0] = jobs[0].c;
        
        for (int i = 1; i < n; i++) {
            int low = 0, high = i - 1;
            while (low < high) {
                int mid = low + (high - low + 1) / 2;
                if (jobs[mid].e <= jobs[i].s) low = mid;
                else high = mid - 1;
            }
            dp[i] = jobs[i].c;
            if (jobs[low].e <= jobs[i].s) dp[i] += dp[low];
            dp[i] = max(dp[i], dp[i - 1]);
        }
        return dp[n - 1];
    }
};

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