0
$\begingroup$

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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.