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

व्याख्या: कार्य 0 (1-3, 500) और कार्य 3 (3-6, 700) चुनें। कुल = 1200।

समाधान दृष्टिकोण (DP + बाइनरी सर्च)

1. कार्यों को समाप्ति समय के अनुसार क्रमबद्ध करें।
2. dp[i] = पहले i कार्यों (क्रमबद्ध क्रम में) से अधिकतम लाभ।
3. प्रत्येक कार्य i के लिए, बाइनरी सर्च से अंतिम कार्य j ढूंढें जहां end[j] ≤ start[i]।
4. dp[i] = max(dp[i-1], profit[i] + dp[j])

कार्यकारी प्रोग्राम

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

struct Job { int s, e, p; };

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

int main() {
    Solution ob;
    vector<int> startTime = {1,2,3,3};
    vector<int> endTime = {3,4,5,6};
    vector<int> profit = {500,100,400,700};
    cout << ob.jobScheduling(startTime, endTime, profit);
    return 0;
}

आउटपुट

1200