We know that there is a greedy algorithm for scheduling $ n $ Jobs for which each job has its own deadline and profit.
In the greedy algorithm we sort the quantity according to their profit descendants. And if a job can add to you
possible set of jobs we add it to the set.
A job can be added to the set if it starts before the deadline and a time window is required for each job.
Are there any $ O (nlogn) $ Algorithm for this problem as follows?
- Sort the amount by profit with Merge Sort in $ O (nlogn) $
- Add the first job to the opportunity set.
- For remaining orders, add the order to the set of its deadline, which is smaller than its index in the set option.
- We have to stay that way
possible setsorted. Then we can add it to the set for each new job
binary searchin the $ O (logn) $
The total cost of the above algorithm is $ O (nlogn) + O (n) * O (logn) = O (nlogn) $
Is this algorithm correct?