C++-এ ওজনযুক্ত জব শিডিউলিং-এ জবগুলো খুঁজে বের করা

Nটি জব দেওয়া আছে যারায় প্রতিটির স্টার্ট টাইম, ফিনিশ টাইম এবং প্রফিট আছে। ওভারল্যাপ না করে সর্বোচ্চ প্রফিটের সাবসেট খুঁজে বের করুন।

ইনপুট: N=4, J={{2,3,55},{4,6,25},{7,20,150},{3,150,250}}

আউটপুট: [(2,3,55),(3,150,250)] এবং সর্বোচ্চ প্রফিট 305

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

• find_no_conflict() ফাংশন দিয়ে বাইনারি সার্চ করে নন-কনফ্লিক্টিং জব খুঁজুন।
• জবগুলো ফিনিশ টাইম অনুযায়ী সর্ট করুন।
• DP টেবিল তৈরি করুন: table[i].value = i-তম জব পর্যন্ত সর্বোচ্চ প্রফিট।
• প্রতিটি জবের জন্য include_profit = job[i].profit + table[l].value (l = non-conflict index)।
• যদি include_profit > table[i-1].value হয় তবে table[i] আপডেট করুন, নয় তবে table[i-1] কপি করুন।
• শেষে table[n-1]- থেকে জবগুলো এবং প্রফিট প্রিন্ট করুন।

উদাহরণ (C++ কোড)

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

class Job { public: int start, finish, profit; };

struct job_with_weight {
    vector job;
    int value;
};

bool jobComparator(Job s1, Job s2) { return s1.finish < s2.finish; }

int find_no_conflict(Job jobs[], int index) {
    int left = 0, right = index - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (jobs[mid].finish <= jobs[index].start) {
            if (jobs[mid+1].finish <= jobs[index].start) left = mid + 1;
            else return mid;
        } else right = mid - 1;
    }
    return -1;
}

int get_max_profit(Job job_list[], int n) {
    sort(job_list, job_list + n, jobComparator);
    job_with_weight table[n];
    table[0].value = job_list[0].profit;
    table[0].job.push_back(job_list[0]);
    for (int i = 1; i < n; i++) {
        int include_profit = job_list[i].profit;
        int l = find_no_conflict(job_list, i);
        if (l != -1) include_profit += table[l].value;
        if (include_profit > table[i-1].value) {
            table[i].value = include_profit;
            table[i].job = table[l].job;
            table[i].job.push_back(job_list[i]);
        } else table[i] = table[i-1];
    }
    cout << "[";
    for (int i=0; i

ইনপুট
{{2,3,55},{4,6,25},{7,20,150},{3,150,250}}

আউটপুট
[(2, 3, 55),(3, 150, 250),] Optimal profit: 305