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:

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