वेटेड जॉब शेड्यूलिंग

विभिन्न जॉब्स की एक सूची दी गई है, उनके प्रारंभ समय, समाप्ति समय और उस जॉब का लाभ भी उन जॉब्स के लिए प्रदान किया गया है। हमारा कार्य जॉब्स का एक सबसेट ढूंढना है, जहां लाभ अधिकतम हो और कोई जॉब एक-दूसरे को ओवरलैप न करे।

इस एल्गोरिदम में, हम सब-प्रॉब्लम्स के परिणाम स्टोर करने के लिए एक टेबल का उपयोग करते हैं और सबप्रॉब्लम्स के परिणामों का उपयोग करके, पूरी समस्या को बॉटम-अप तरीके से हल किया जा सकता है।

इस एल्गोरिदम की समय जटिलता O(n²) है, लेकिन हम इसे बाइनरी सर्च मेथड का उपयोग करके नॉन-कॉन्फ्लिक्टिंग जॉब्स खोजने के लिए O(n Log n) में बदल सकते हैं।

इनपुट और आउटपुट

इनपुट: कुछ जॉब्स का प्रारंभ समय, समाप्ति समय और लाभ मैट्रिक्स रूप में। और जॉब्स की संख्या। यहां 4 जॉब्स मौजूद हैं।
3  5  25
1  2  50
6  15 75
2  100 100

आउटपुट: अधिकतम लाभ 150। जॉब क्रम है जॉब 2, जॉब 4, या जॉब 2, जॉब 1, जॉब 3। दोनों मामलों में अधिकतम लाभ 150 है।

एल्गोरिदम

findMaxProfit(jobList, n)

इनपुट: जॉब लिस्ट और जॉब्स की संख्या
आउटपुट: जॉब्स से अधिकतम लाभ

शुरुआत
    जॉब लिस्ट को उनके समाप्ति समय के अनुसार सॉर्ट करें
    परिणाम स्टोर करने के लिए टेबल परिभाषित करें
    table[0] := jobList[0].profit
    i := 1 से n-1 तक, करें
        addProfit := jobList[i].profit
        nonConflict := उन जॉब्स को ढूंढें जो दूसरों के साथ कॉन्फ्लिक्ट नहीं कर रहे
        यदि कोई नॉन-कॉन्फ्लिक्टिंग जॉब मिला, तो
            addProfit := addProfit + table[nonConflict]
        यदि addProfit > table[i - 1], तो
            table[i] := addProfit
        अन्यथा
            table[i] := table[i-1]
    पूर्ण
    result := table[n-1]
    वापस result
अंत

उदाहरण (C++ कोड)

#include <iostream>
#include <algorithm>
using namespace std;

struct Job {
    int start, end, profit;
};

bool comp(Job job1, Job job2) {
    return (job1.end < job2.end);
}

int nonConflictJob(Job jobList[], int i) {
    for (int j = i-1; j >= 0; j--) {
        if (jobList[j].end <= jobList[i].start)
            return j;
    }
    return -1;
}

int findMaxProfit(Job jobList[], int n) {
    sort(jobList, jobList+n, comp);
    int *table = new int[n];
    table[0] = jobList[0].profit;
    
    for (int i = 1; i < n; i++) {
        int addProfit = jobList[i].profit;
        int l = nonConflictJob(jobList, i);
        if (l != -1)
            addProfit += table[l];
        table[i] = (addProfit > table[i-1]) ? addProfit : table[i-1];
    }
    
    int result = table[n-1];
    delete[] table;
    return result;
}

int main() {
    Job jobList[] = {
        {3, 5, 25},
        {1, 2, 50},
        {6, 15, 75},
        {2, 100, 100}
    };
    int n = 4;
    cout << "The maximum profit: " << findMaxProfit(jobList, n);
    return 0;
}

आउटपुट

The maximum profit: 150