MergeIntervals.java

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

public class MergeIntervals {

    private static class Interval {
        public int start;
        public int end;

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

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

    public static void main(String[] args) {
        List<Interval> intervals = new ArrayList<Interval>();
        intervals.add(new Interval(6, 8));
        intervals.add(new Interval(10, 15));
        intervals.add(new Interval(4, 6));
        intervals.add(new Interval(1, 2));

        List<Interval> mergedIntervals = mergeIntervals(intervals);
        System.out.println(mergedIntervals);
    }

    private static List<Interval> mergeIntervals(List<Interval> intervals) {
        Collections.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                return o1.start - o2.start;
            }
        });

        ArrayList<Interval> mergedIntervals = new ArrayList<Interval>();
        mergedIntervals.add(intervals.get(0));
        for (Interval interval : intervals) {
            Interval lastMergedInterval = mergedIntervals.get(mergedIntervals.size() - 1);

            if (overlaps(interval, lastMergedInterval)) {
                lastMergedInterval.start = Math.min(interval.start, lastMergedInterval.start);
                lastMergedInterval.end = Math.max(interval.end, lastMergedInterval.end);
            }
            else {
                mergedIntervals.add(interval);
            }
        }

        return mergedIntervals;
    }

    private static boolean overlaps(Interval interval1, Interval interval2) {
        if (interval1.start >= interval2.start && interval1.start <= interval2.end) {
            return true;
        }

        if (interval2.start >= interval1.start && interval2.start <= interval1.end) {
            return true;
        }

        return false;
    }
}