डेडलाइन के साथ जॉब सीक्वेंसिंग प्रॉब्लम

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

इस समस्या को हल करने के लिए, जॉब्स के सेट के सभी सबसेट उत्पन्न किए जाते हैं ताकि यह जांचा जा सके कि व्यक्तिगत सबसेट व्यवहार्य है या नहीं। साथ ही, उत्पन्न सभी व्यवहार्य सबसेट के लिए अधिकतम प्रॉफिट पर नज़र रखें।

इस एल्गोरिदम की टाइम कॉम्प्लेक्सिटी O(n^2) है।

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

इनपुट: जॉब्स की लिस्ट जॉब आईडी, डेडलाइन और प्रॉफिट के साथ। और जॉब्स की संख्या n।
{('a', 2, 100), ('b', 1, 19), ('c', 2, 27), ('d', 1, 25), ('e', 3, 15)}
n = 5
आउटपुट: अधिकतम प्रॉफिट जॉब सीक्वेंस का क्रम: c a e

एल्गोरिदम

jobSequence(jobList, n)

इनपुट: जॉब्स की लिस्ट और लिस्ट में मौजूद जॉब्स की संख्या।
आउटपुट: वह क्रम, जिसमें जॉब्स ली जाती हैं।

Begin
    जॉब्स को jobList में उनके प्रॉफिट के अनुसार सॉर्ट करें
    जॉब सीक्वेंस की एक लिस्ट और फ्री टाइम स्लॉट्स को ट्रैक करने के लिए स्लॉट बनाएं
    प्रारंभ में सभी स्लॉट्स को फ्री बनाएं
    for all given jobs i do
        for all jobs in the list from ending of the list do
            if slot[j] is free then
                jobSequence[j] := i
                make slot[j] := fill
                break the loop
            done
        done
    done
    for all slots when it is not free do
        print id of job using jobList[jobSequence[i]]
    done
End

उदाहरण

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

struct Job {
    char id;
    int deadLine;
    int profit;
};

bool comp(Job j1, Job j2) {
    return (j1.profit > j2.profit);
    // प्रॉफिट के आधार पर जॉब्स की तुलना करें
}

int min(int a, int b) {
    return (a < b) ? a : b;
}

void jobSequence(Job jobList[], int n) {
    sort(jobList, jobList + n, comp);
    // jobList को प्रॉफिट पर सॉर्ट करें
    int jobSeq[n];
    // परिणाम स्टोर करने के लिए (जॉब्स का क्रम)
    bool slot[n];
    // फ्री टाइम स्लॉट्स को ट्रैक करने के लिए
    for (int i = 0; i < n; i++)
        slot[i] = false; // प्रारंभ में सभी स्लॉट्स फ्री हैं
    for (int i = 0; i < n; i++) {
        // सभी दी गई जॉब्स के लिए
        for (int j = min(n, jobList[i].deadLine) - 1; j >= 0; j--) {
            // अंतिम फ्री स्लॉट से खोजें
            if (slot[j] == false) {
                jobSeq[j] = i; // इस जॉब को जॉब सीक्वेंस में जोड़ें
                slot[j] = true; // इस स्लॉट को ऑक्यूपाइड मार्क करें
                break;
            }
        }
    }
    for (int i = 0; i < n; i++)
        if (slot[i])
            cout << jobList[jobSeq[i]].id << " "; // सीक्वेंस प्रदर्शित करें
}

int main() {
    Job jobList[] = {{'a', 2, 100}, {'b', 1, 19}, {'c', 2, 27}, {'d', 1, 25}, {'e', 3, 15}};
    int n = 5;
    cout << "अधिकतम प्रॉफिट जॉब सीक्वेंस का क्रम: ";
    jobSequence(jobList, n);
}

आउटपुट

अधिकतम प्रॉफिट जॉब सीक्वेंस का क्रम: c a e