# Looking for the name of this job scheduling algorithm

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.

• 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. – 89f3a1c Aug 8 '19 at 4:05

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.)