ডেডলাইন সহ জব সিকোয়েন্সিং সমস্যা (Job Sequencing with Deadlines)

এই সমস্যায় জবের একটি লিস্ট দেওয়া থাকে, প্রতিটি জবের জন্য ডেডলাইন এবং প্রফিট দেওয়া থাকে। প্রতিটি জব ১ ইউনিট টাইম নেয়, তাই মিনিমাম ডেডলাইন ১। একবারে একটি জব শিডিউল করা যায়। লক্ষ্য হলো ম্যাক্সিমাম প্রফিট অর্জন।

সমাধান: সব সাবসেট জেনারেট করে ফিজিবিলিটি চেক করা হয় এবং ম্যাক্সিমাম প্রফিট ট্র্যাক করা হয়। টাইম কমপ্লেক্সিটি O(n²)।

ইনপুট এবং আউটপুট

Input: Jobs: {('a',2,100), ('b',1,19), ('c',2,27), ('d',1,25), ('e',3,15)}, n=5
Output: Maximum profit sequence: c a e

অ্যালগরিদম

jobSequence(jobList, n)
Input: জব লিস্ট, জব সংখ্যা
Output: জব সিকোয়েন্স

Begin
    jobList-কে প্রফিট অনুযায়ী সর্ট করুন
    jobSeq এবং slot অ্যারে তৈরি করুন (ফ্রি টাইম স্লট ট্র্যাক করতে)
    সব স্লট ফ্রি হিসেবে ইনিশিয়ালাইজ করুন
    for all jobs i do
        for j from min(n, jobList[i].deadline)-1 down to 0 do
            if slot[j] is free then
                jobSeq[j] := i
                slot[j] := filled
                break
            done
        done
    done
    for all slots where not free do
        print jobList[jobSeq[i]].id
    done
End

C++ উদাহরণ

#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=0; j--) {
            if(slot[j]==false) {
                jobSeq[j] = i; slot[j] = true; break;
            }
        }
    }
    for(int i=0; i

Following is maximum profit sequence of job sequence: c a e