C++ এ ওয়েটেড জব শিডিউলিংয়ের সাথে জড়িত চাকরি খুঁজুন

ধরুন আমাদের কাছে N কাজের একটি তালিকা রয়েছে যেখানে প্রতিটি কাজের তিনটি প্যারামিটার রয়েছে। 1. শুরুর সময় 2. শেষ সময় 3. লাভ আমাদের সর্বাধিক লাভের সাথে যুক্ত কাজের একটি উপসেট খুঁজে বের করতে হবে যাতে উপসেট ওভারল্যাপে দুটি কাজ না হয়৷

সুতরাং, যদি ইনপুট হয় 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() সংজ্ঞায়িত করুন, এটি একটি অ্যারে কাজ, সূচক,

• বাম :=0, ডানে :=সূচক - 1

• যখন বামে <=ডানে, কর −

  • মধ্য :=(বাম + ডান) / 2

  • যদি jobs[mid].finish <=jobs[index].start হয়, তাহলে -

    • যদি কাজ [মাঝ + 1].সমাপ্ত হয় <=কাজ [সূচী].শুরু, তারপর -

      • বাম :=মধ্য + 1

    • মাঝামাঝি ফেরত

      • মাঝামাঝি ফেরত

  • অন্যথায়

    • ডান:=মধ্য - 1

• রিটার্ন -1

• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -

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

• কাজের জন্য একটি টেবিল তৈরি করুন যার নাম টেবিল অফ সাইজ n

• টেবিল[0].value :=job_list[0].লাভ

• টেবিলের শেষে job_list[0] সন্নিবেশ করুন[0]

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

  • অন্তর্ভুক্ত_লাভ :=চাকরির_তালিকা[i].লাভ

  • l :=find_no_conflict(কাজের_তালিকা, i)

  • যদি l - 1 এর সমান না হয়, তাহলে −

    • Include_profit :=include_profit + টেবিল[l].value

  • যদি include_profit> table[i - 1].value হয়, তাহলে −

    • টেবিল[i].মান :=অন্তর্ভুক্ত_লাভ

    • table[i].job :=টেবিল[l].job

    • টেবিলের শেষে job_list[i] সন্নিবেশ করান[i]

  • অন্যথায়

    • টেবিল[i] :=টেবিল[i - 1]

• টেবিল থেকে কাজ প্রদর্শন করুন

• সর্বোত্তম লাভ প্রদর্শন করুন :=টেবিল[n - 1].value

উদাহরণ (C++)

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#include <bits/stdc++.h>
using namespace std;
class Job {
   public:
      int start, finish, profit;
};
struct job_with_weight {
   vector<Job> 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<table[n-1].job.size(); i++) {
      Job j = table[n-1].job[i];
      cout << "(" << j.start << ", " << j.finish << ", " << j.profit << "),";
   }
   cout << "]\nOptimal profit: " << table[n - 1].value;
}
int main() {
   Job arr[] = {{2, 3, 55},{4, 6, 25},{7, 20, 150},{3, 150, 250}};
   int n = sizeof(arr)/sizeof(arr[0]);
   get_max_profit(arr, n);
}

ইনপুট

{{2, 3, 55},{4, 6, 25},{7, 20, 150},{3, 150, 250}}

আউটপুট

[(2, 3, 55),(3, 150, 250),]
Optimal profit: 305