Answer:
The best algorithm to follow here will be the Greedy algorithm.
•We have to generate subsets of the jobs and check them all.
•We also have to keep track of the maximum profit.
•That is we take the best local solution first.
•That is why the greedy algorithm is a good fit for this job.
Description and Pseudo Code>>
•First, we have to sort all the jobs in decreasing order of the profit.
•Second, we have to initialize the result sequence as the first job in the sorted jobs section.
•Now if the current job can be fitted in the deadline, then it is added to the result otherwise ignore it.
Pseudo Code>.
printJobSchedule(jobs){
sort (arr); //sort all the jobs in decreasing order
for all the given jobs do
find a free slot for the job
if free slot found then
add the job to result
slot == full
end if
end
Time Complexity of the algorithm is >>
O(n^2)
This can be further optimized by using disjoint set.
Explanation:
