Interval Partitioning

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 - intPartSchedule(Job[] jobs)

Input - An array of jobs to be scheduled.

Output - A list of processors containing the 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.

        // Initialize the processor list and add the first processor to it.
        List<Processor> processors = new ArrayList<>();
        processors.add(new Processor());

        for (i = 0 to jobs.length)
            for (k = 0 to processors.length)
                if (job[i] is compatible with processors.get(k))
                    processors.get(k).add(job[i])
                    break
                else
                    // Create a new processor, then add the job to the
                    // last processor in the list as that is the new processor.
                    processors.add(new Processor())
                    processors.getLast().add(job[i])

        return processors