ডেডলাইন ও সময়কাল দেওয়া থাকলে কাজের সর্বোত্তম শিডিউল#

ধরো, আমাদের কাছে কাজের একটি সেট আছে, এবং আমরা প্রতিটি কাজের ডেডলাইন ও সময়কাল জানি। একটি কাজ শেষ হওয়ার আগে থামানো যাবে না। সর্বাধিক সংখ্যক কাজ কমপ্লিট করার জন্য এমন একটি শিডিউল তৈরি করতে হবে।

সমাধান#

সমাধানের অ্যালগরিদমটি গ্রিডি (greedy)। চলো সমস্ত কাজকে তাদের ডেডলাইন অনুসারে সাজাই এবং নিম্নক্রমে দেখি। এছাড়াও, একটি কিউ $q$ তৈরি করি, যেখানে আমরা ধীরে ধীরে কাজগুলো রাখব এবং সবচেয়ে কম চলার সময়ের কাজটি বের করব (উদাহরণস্বরূপ, আমরা set বা priority_queue ব্যবহার করতে পারি)। শুরুতে, $q$ খালি।

ধরো, আমরা $i$-তম কাজটি দেখছি। প্রথমত, এটাকে $q$-তে রাখি। $i$-তম কাজের ডেডলাইন এবং $i-1$-তম কাজের ডেডলাইনের মধ্যবর্তী সময়কাল কনসিডার করি। এটা কিছু দৈর্ঘ্য $T$-এর একটি সেগমেন্ট। আমরা $q$ থেকে কাজ বের করব (তাদের অবশিষ্ট সময়কালের ঊর্ধ্বক্রমে) এবং সম্পাদন করব যতক্ষণ না সম্পূর্ণ সেগমেন্ট $T$ পূর্ণ হয়। গুরুত্বপূর্ণ: যদি কোনো সময়ে বের করা কাজটি সেগমেন্ট $T$ পূর্ণ হওয়া পর্যন্ত কেবল আংশিকভাবে সম্পাদন করা যায়, তাহলে আমরা সেই কাজটি যতটা সম্ভব আংশিকভাবে সম্পাদন করি, অর্থাৎ $T$-সময়কাল ধরে, এবং কাজের বাকি অংশ $q$-তে ফেরত রাখি।

অ্যালগরিদম কমপ্লিট হলে আমরা সর্বোত্তম সমাধান (বা, কয়েকটি সমাধানের মধ্যে অন্তত একটি) পাব। অ্যালগরিদমের রানিং টাইম হলো $O(n \log n)$।

ইমপ্লিমেন্টেশন#

নিচের ফাংশনটি কাজের একটি ভেক্টর (ডেডলাইন, সময়কাল এবং কাজের ইনডেক্স সমন্বিত) নেয় এবং সর্বোত্তম শিডিউলে ব্যবহৃত সমস্ত কাজের ইনডেক্স সম্বলিত একটি ভেক্টর গণনা করে। লক্ষ্য করো যে তুমি যদি স্পষ্টভাবে পরিকল্পনা লিখতে চাও তাহলে এই কাজগুলোকে এখনও তাদের ডেডলাইন অনুসারে সাজাতে হবে।

struct Job {
    int deadline, duration, idx;

    bool operator<(Job o) const {
        return deadline < o.deadline;
    }
};

vector<int> compute_schedule(vector<Job> jobs) {
    sort(jobs.begin(), jobs.end());

    set<pair<int,int>> s;
    vector<int> schedule;
    for (int i = jobs.size()-1; i >= 0; i--) {
        int t = jobs[i].deadline - (i ? jobs[i-1].deadline : 0);
        s.insert(make_pair(jobs[i].duration, jobs[i].idx));
        while (t && !s.empty()) {
            auto it = s.begin();
            if (it->first <= t) {
                t -= it->first;
                schedule.push_back(it->second);
            } else {
                s.insert(make_pair(it->first - t, it->second));
                t = 0;
            }
            s.erase(it);
        }
    }
    return schedule;
}