# Job Scheduling with deadline with $nlogn$ algorithm

We know that there is a Greedy algorithm for scheduling of $$n$$ jobs which each job has its own deadline and profit.

In greedy algorithm, we sort the set by their profit descendant, And if a job can add to a possible set of jobs, we add it to the set.

A job can be added to the set, if it starts before its deadline and each work need 1 time slot for doing.

Is there any $$O(nlogn)$$ algorithm for this problem as follows?

• Sorting the set by their profit using merge sort in $$O(nlogn)$$
• Add the first job to the possibility set.
• For remain jobs, add the job to the set of its deadline is less than its index in possibility set.
• We have to remain the possible set sorted. Then for each new coming job, we can add it to the set using binary search in $$O(logn)$$

Total cost of the above algorithm is $$O(nlogn)+O(n)*O(logn)=O(nlogn)$$

Is this algorithm correct?

• What do you mean exactly by "set" ? It seems there are different types of set in your explanation. Commented Jan 9, 2020 at 15:53
• We discourage "is my algorithm correct?" questions, as the only possible answer is yes/no, which is unlikely to be useful to future visitors. The way to tell whether your algorithm is correct is to prove it correct. See cs.stackexchange.com/q/59964/755. I suggest you give that a try, and if you get stuck at any particular point, ask about that specific aspect of the proof.
– D.W.
Commented Jan 9, 2020 at 17:35