Merge Intervals

Question (LC.56)

Give a list of time intervals, return a list of merged time intervals.

Example

I: [[1,3], [2,6], [8,10], [15,18]]
O: [[1,6], [8,10], [15,18]]

I: [[3,4], [1,5]]
O: [[1,5]]

The input is not sorted.

Approach

Sort by start time. Scan from left to right keep a start and end for merged interval. Update the end time (make sure it's larger) until no intersecting intervals.

Code

public List<Interval> merge(List<Interval> intervals) {
    List<Interval> results = new ArrayList<>();
    // edge check
    if (intervals == null || intervals.size() == 0) {
        return results;
    }
    // sort by start time
    Collections.sort(intervals, (Interval i1, Interval i2) -> i1.start - i2.start);
    // scan sorted intervals
    int mergeStartTime = intervals.get(0).start;
    int mergeEndTime = intervals.get(0).end;
    for (Interval intv : intervals) {
        if (intv.start <= mergeEndTime) {
            mergeEndTime = Math.max(mergeEndTime, intv.end);
        } else {
            results.add(new Interval(mergeStartTime, mergeEndTime));
            mergeStartTime = intv.start;
            mergeEndTime = intv.end;
        }
    }
    results.add(new Interval(mergeStartTime, mergeEndTime));
    return results;
}

Complexity

Time O(nlogn) + O(n) Space O(1)