Interval Scheduling

Input: set of intervals on the line, represented by pairs of points (ends of intervals).

Output: finding the largest set of intervals such that none two of them overlap.

Java
Time complexity: O(N log N)
Space complexity: O(N)

public class IntervalScheduling {

    static class Interval{
        private int start;
        private int finish;

        public Interval(int start, int finish){
            this.start = start;
            this.finish = finish;
        }

        public int getStart(){
            return start;
        }

        public int getFinish(){
            return finish;
        }

        @Override
        public String toString(){
            return "[" + start + ", " + finish + "]";
        }
    }

    public List<Interval> maxNonOverlap(List<Interval> intervals){
        if (intervals == null || intervals.size() == 0){
            return Collections.EMPTY_LIST;
        }

        intervals.sort((Interval i1, Interval i2)->i1.getFinish() - i2.getFinish());

        List<Interval> res = new ArrayList<>();
        res.add(intervals.get(0));
        int ptr = 1;

        while (ptr < intervals.size()){
            Interval curr = res.get(res.size() - 1);
            while (ptr < intervals.size() && intervals.get(ptr).getStart() < curr.getFinish()){
                ++ptr;
            }
            if (ptr < intervals.size()){
                res.add(intervals.get(ptr++));
            }
        }

        return res;

    }

    public static void main(String[] args) {
        List<Interval> intervals = new ArrayList<>();
        intervals.add(new Interval(600, 830));
        intervals.add(new Interval(800, 900));
        intervals.add(new Interval(900, 1100));
        intervals.add(new Interval(900, 1130));
        intervals.add(new Interval(1030, 1400));
        intervals.add(new Interval(1230, 1400));

        List<Interval> nonOverlapIntervals = new IntervalScheduling().maxNonOverlap(intervals);
        System.out.println((Iterable) nonOverlapIntervals);

    }

}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s