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?

  • $\begingroup$ What do you mean exactly by "set" ? It seems there are different types of set in your explanation. $\endgroup$
    – Optidad
    Jan 9, 2020 at 15:53
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Jan 9, 2020 at 17:35


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.