Merge Intervals

Question (LC.56)

Given a collection of intervals, merge all overlapping intervals.

Example

Input: [ [1,3],[2,6],[8,10],[15,18] ]
Return: [ [1,6],[8,10],[15,18] ]

Analysis

Is the input sorted? No. Then how should we sort it? We want to merge the intervals that overlap. This can be a derivative from the classic schedule task question? We sorted by start time. Then, we check if the next end time overlaps with the current end time. If it does, we merge them by updating the max end time. If it does not, we add the next interval to our results and update the current end time. This kind of greedy approach guarantees "optimal" at each step.

Code

public class MergeIntervals {

    // Definition for an interval.
    public class Interval {
        int start;
        int end;
        Interval() { start = 0; end = 0; }
        Interval(int s, int e) { start = s; end = e; }
    }

    public Comparator<Interval> IntervalComparator = new Comparator<Interval>() {
        @Override
        public int compare(Interval i1, Interval i2) {
            return i1.start - i2.start; // Integer.compare
        }
    };

    public List<Interval> merge(List<Interval> intervals) {
        // no need to merge
        if (intervals.size() < 2) {
            return intervals;
        }

        Collections.sort(intervals, IntervalComparator);
        List<Interval> results = new LinkedList<>();
        int curStart = intervals.get(0).start;
        int curEnd = intervals.get(0).end;

        for (Interval intv : intervals) {
            if (intv.start <= curEnd) { // overlap
                curEnd = Math.max(curEnd, intv.end);
            } else {
                results.add(new Interval(curStart, curEnd));
                curStart = intv.start;
                curEnd = intv.end;
            }
        }

        // only add when encountering a disjoint interval
        results.add(new Interval(curStart, curEnd));
        return results;
    }

}

Time Complexity

Sorting takes O(nlogn) and the merging is just one iteration so O(n). The total time complexity is O(nlogn).