Each of the n projects must be completed in the next D days or you lose its contract. Unfortunately, you do not have enough time to complete all the projects. Your goal is to select a subset S of the projects to complete that will maximize the total fees you earn in D days.

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.