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

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

সমাধান#

সমাধানের অ্যালগরিদমটি গ্রিডি। আসুন সমস্ত কাজকে তাদের ডেডলাইন অনুসারে সাজাই এবং নিম্নক্রমে দেখি। এছাড়াও, একটি কিউ $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;
}