# Interval Scheduling

4/December/2015 by Valkryst, Updated 29/June/2017

The following post is derived from notes taken while reading through this textbook.

## Assumptions and Statements:

- We have a set of jobs to schedule where each has a start time and an end time.
- We want to find a subset of jobs that has as many scheduled jobs, within it, as possible.
- Two jobs are compatible if their running times do not overlap, so a job that starts at time 1 and ends at time 3 is not compatible with a job that starts at time 2 and ends at time 6.

## Algorithm:

**Algorithm** - intSchedule(Job[] jobs)

**Input** - An array of jobs to be scheduled.

**Output** - An array of jobs that have been scheduled in the order that they finish and to have the optimal amount scheduled jobs.

` ````
Sort the jobs by their ending times from earliest to latest end time.
The first job to end will be at the beginning of the array.
The last job to end will be at the end of the array.
for (i = 0 to n)
if (jobs[i] compatible with R)
Add jobs[i] to the set of scheduled jobs, R.
end
end
return R
```