Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

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() परिभाषित करें, यह जॉब्स की एक सरणी, सूचकांक लेगा,

  • left := 0, right := index - 1

  • जब left <= right, तब तक करें −

    • mid := (left + right) / 2

    • यदि jobs[mid].finish <= jobs[index].start, तो −

      • यदि jobs[mid + 1].finish <= jobs[index].start, तो −

        • left := mid + 1

      • mid लौटाएं

        • mid लौटाएं

    • अन्यथा

      • right := mid - 1

  • -1 लौटाएं

  • मुख्य विधि से, निम्नलिखित करें −

  • समाप्ति समय के आधार पर जॉब_लिस्ट सरणी को सॉर्ट करें

  • जॉब्स के लिए n आकार की एक टेबल बनाएं जिसे टेबल कहा जाता है

  • table[0].value := job_list[0].profit

  • job_list[0] को table[0] के अंत में डालें

  • i := 1 से इनिशियलाइज़ करें, जब i < n, अपडेट करें (i को 1 से बढ़ाएं), तब तक करें −

    • include_profit := job_list[i].profit

    • l := find_no_conflict(job_list, i)

    • यदि l -1 के बराबर नहीं है, तो −

      • include_profit := include_profit + table[l].value

    • यदि include_profit > table[i - 1].value, तो −

      • table[i].value := include_profit

      • table[i].job := table[l].job

      • job_list[i] को table[i] के अंत में डालें

    • अन्यथा

      • table[i] := table[i - 1]

  • टेबल से जॉब्स प्रदर्शित करें

  • इष्टतम लाभ प्रदर्शित करें := table[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

  1. C++ में डुप्लिकेट उपट्री ढूंढना C++ में डुप्लिकेट उपट्री ढूंढना

    मान लीजिए हमारे पास एक बाइनरी ट्री है। हमें सभी डुप्लिकेट उपट्री ढूंढने हैं। इसलिए प्रत्येक प्रकार के डुप्लिकेट उपट्री के लिए, हमें उनमें से किसी एक का रूट नोड लौटाना है। मान लीजिए हमारे पास ऐसा ट्री है: डुप्लिकेट उपट्री हैं: हल का दृष्टिकोण इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

  1. C++ प्रोग्राम शॉर्टेस्ट जॉब फर्स्ट (SJF) शेड्यूलिंग (प्रीमेप्टिव) के लिए C++ प्रोग्राम शॉर्टेस्ट जॉब फर्स्ट (SJF) शेड्यूलिंग (प्रीमेप्टिव) के लिए

    प्रक्रिया, प्रक्रिया का बर्स्ट समय और एक क्वांटम सीमा दी गई है; कार्य प्रीमेप्टिव शॉर्टेस्ट जॉब फर्स्ट शेड्यूलिंग विधि का उपयोग करके प्रतीक्षा समय, टर्नअराउंड समय और उनके संबंधित औसत समय को खोजना और प्रिंट करना है।शॉर्टेस्ट जॉब फर्स्ट शेड्यूलिंग क्या है?शॉर्टेस्ट जॉब फर्स्ट शेड्यूलिंग वह जॉब या प्रो

  1. C++ प्रोग्राम शॉर्टेस्ट जॉब फर्स्ट (SJF) शेड्यूलिंग (नॉन-प्रीमेप्टिव) के लिए C++ प्रोग्राम शॉर्टेस्ट जॉब फर्स्ट (SJF) शेड्यूलिंग (नॉन-प्रीमेप्टिव) के लिए

    प्रक्रिया, प्रक्रिया का बर्स्ट समय और एक क्वांटम सीमा दी गई है; कार्य नॉन-प्रीमेप्टिव शॉर्टेस्ट जॉब फर्स्ट शेड्यूलिंग विधि का उपयोग करके प्रतीक्षा समय, टर्नअराउंड समय और उनके संबंधित औसत समय को खोजना और प्रिंट करना है।शॉर्टेस्ट जॉब फर्स्ट शेड्यूलिंग क्या है?शॉर्टेस्ट जॉब फर्स्ट शेड्यूलिंग वह जॉब या