Interval Scheduling Algorithm

Interval Scheduling Algorithm

Any interval has two time stamps, it’s start time and end time. To schedule number of intervals on to particular resource, take care that no two intervals are no overlapping, that is to say second interval cannot be scheduled while first is running. Given a set of intervals S with their start time si and end time ei, find out largest set R such that all events in R are mutually compatible. Two intervals are called compatible if they do not overlap (2nd job starts after or at the same time as the 1st one finishes). This problem is called as interval scheduling problem and algorithm which helps solve this class of problems is called as interval scheduling algorithm.
Example: 8 intervals{A,B,C,D,E,F,G,H}, optimal set would be {B,E,H}

interval scheduling

Interval Scheduling : Line of thought

Notice from problem statement that ask is to maximize output with given constraints. What template this kind of problems fit in? It’s greedy algorithm. We need to select each job which maximizes output, i.e gives us maximum number of compatible intervals. What should be the order of evaluation of intervals? There are some natural orders we can think of :
1. Order intervals by earliest start time first.
2. Order intervals by earliest end time first.
3. Order intervals by minimum number of overlapping jobs.
4. Order intervals by shortest job first.

Let’s take some examples and see how things work out with each criteria.
1. Earliest start time first

interval scheduling algorithm

In above arrangement, if we schedule interval with earliest start time first, only one interval will scheduled, however, optimally, 3 intervals, { B, C, D } should have been scheduled.

2. Minimum number of conflicting jobs

interval scheduling problem

If we select job with least conflicts first, we will select F ( 2 conflicts) then C ( with 3 conflicts ) and then E ( again with 3 conflicts ). However, ideal set should be { B, C, D, E }

3. Shortest job first.

In this case, if we select shortest job first, set will contain only interval A, where as optimal set is {B, C}.
These are counter examples for three of the four natural ordering, these three criteria cannot give us optimum output, which is maximum number of compatible intervals. If we take interval with earliest end time, it will give us optimal set. Can you check if above three examples give you correct answer if you take interval based on earliest end time first? If we take first example, when order by end time, intervals will look like this. From this we can easily find out that compatible intervals are B, E and H.

Interval scheduling algorithm

Sort all jobs which based on end time in increasing order.

  1. Take the interval which has earliest finish time.
  2. Repeat net two steps till all you process all jobs
  3. Eliminate all intervals which have start time less than selected interval’s end time.
  4. If interval has start time greater than current interval’s end time, at it to set. Set current interval to new interval
package com.company;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created by sangar on 25.4.18.
 */
public class IntervalScheduling {
    public static ArrayList<Interval> intervalScheduling(ArrayList<Interval> intervals){
        Collections.sort(intervals, Comparator.comparing(p -> p.getEndTime()));

        ArrayList<Interval> resultList = new ArrayList<>();

        for(Interval currentInterval : intervals) {
            if(resultList.isEmpty()) resultList.add(currentInterval);
            else{
                if(currentInterval.getStartTime() > resultList.get(resultList.size()-1).getEndTime()){
                    resultList.add(currentInterval);
                }
            }
        }
        return resultList;
    }

    public static void main(String args[] ) throws Exception {
        ArrayList<Interval> intervals = new ArrayList<>();

        intervals.add(new Interval(930,1100));
        intervals.add(new Interval(930,1300));
        intervals.add(new Interval(930,1100));
        intervals.add(new Interval(1130,1300));
        intervals.add(new Interval(1100,1400));
        intervals.add(new Interval(1330,1500));
        intervals.add(new Interval(1330,1500));
        intervals.add(new Interval(1430,1700));
        intervals.add(new Interval(1530,1700));

        ArrayList<Interval> compatibleIntervals = intervalScheduling(intervals);

        for(Interval interval : compatibleIntervals) {
            System.out.println("(" + interval.getStartTime() + "," + interval.getEndTime() + ")");
        }
    }
}

Complexity of algorithm is dominated by the sorting which is O(N log N) which is actually the complexity of sort algorithm.

Reference 
http://courses.cs.vt.edu/cs5114/spring2009/lectures/lecture04-greedy-scheduling.pdf

Please share if you find something missing or wrong. If you want to contribute to algorithm and me and share your knowledge with thousands of students across world, please reach out to us at communications@algorithmsandme.com