Leetcode: Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

Understand the problem:
For question asks for given a collection of intervals, merge all overlapping intervals. So the crux of the problem is to understand "what is the overlapping intervals"? Let's take look at several examples:

For the intervals [1, 3], [2, 6], they are overlapped, because the left boundary of the second token is less than the right boundary of the first token. 

For the intervals [2, 6], [8, 10], they are not overlapped, because again, the left boundary of the second token is greater than the right boundary of the first token. 

Therefore, one method to know if two intervals are overlapped is to first sort the list of intervals according to the left boundary, then compare the left boundary of the second interval with the right boundary of the first interval.

Then, the next question is after we decided two intervals overlapped, how can we merge them together? A easy way is to choose the minimum value of the left boundary, and maximum value of the right boundary. For example, for [1, 3] and [2, 6], the merged interval is [1, 6]. 

Solution:
According to the analysis above, the solution is quite straight-forward. We first sort the array list according to the start value of the Interval. Then check if two intervals are overlapped, if yes, merge together.

Code (Java):

/**
 * 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 class Solution {
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        ArrayList<Interval> result = new ArrayList<Interval>();
        if (intervals == null || intervals.size() == 0) {
            return result;
        }
        
        Collections.sort(intervals, new IntervalComparator());
        
        Interval prev = intervals.get(0);
        for (int i = 1; i < intervals.size(); i++) {
            Interval curr = intervals.get(i);
            if (isOverlapped(curr, prev)) {
                prev.start = prev.start;
                prev.end = Math.max(curr.end, prev.end);
            } else {
                result.add(prev);
                prev = curr;
            }
        }
        
        result.add(prev);
        return result;
    }
    
    private boolean isOverlapped(Interval curr, Interval prev) {
        return curr.start <= prev.end;
    }
    
    private class IntervalComparator implements Comparator<Interval> {
        public int compare(Interval a, Interval b) {
            return a.start - b.start;
        }
    }
}

Discussion:
Since we sort the list once before, the time complexity bounded by O(nlogn). For the space complexity, we only allocated a new list to store the results, so the space complexity at worst case is O(n). That is the best space complexity we can do required by this question.

Summary:
The take away message of the solution is to utilize the advantage of sorted array. Also, make sure you are familiar with sorting objects in Java.