0
$\begingroup$

You have a list of jobs.

Each job has a deadline and an associated profit if completed before the deadline.

Also, each job takes 1 unit of time to complete, and only one job can be completed at any given time (ie single thread)

You are required to choose which jobs to complete such that profits are maximised.

This isn't for homework, just my own interest really. I want to find any resources on this problem or algorithms to solve it. It is similar to the interval scheduling problem, but not quite the same.

Any help would be appreciated.

$\endgroup$
  • $\begingroup$ Are you familiar with Tardos' Algorithm Design book? I'm not sure if they analyzed exactly this problem, but they did many of this kind. $\endgroup$ – 89f3a1c Aug 8 at 4:05
0
$\begingroup$

I don't know the name of the problem, but I do know the solution - this is the same problem that I had to solve for my algorithms course, just different terminology. The problem allows for a greedy choice. If you merely wanted a hint, then stop reading here because below is the solution.

Greedy choice: you schedule the job with maximum profit on its deadline. (If jobs should be finished before the deadline, e.g. job 1 should be done before $t = 2$, then simply subtract one from the associated deadline.)

The algorithm is pretty much working backwards in deadlines, (starting at the latest deadline) scheduling the job with highest profit available on that deadline (this boils down to the greedy choice).

I will leave the proof of the greedy choice as an exercise (read, I don't have a proper keyboard available, which isn't too great for my RSI, so I cannot write it now).

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.