Leetcode/各大家 -- 56. Merge Interval(Comparator)

56. Merge Intervals(Comparator)
medium
https://leetcode.com/problems/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]. 

 LinkedIn Google Facebook Twitter Microsoft Bloomberg Yelp

思路： Use Collections.sort to sort interval by start time using comparator.
           Then loop through each interval, when there pre end >= new start(intersection), merge it.
           Else add the pre interval to list.  After loop, add the last interval to list.
Complexity: Time O(N) Space O(N)

/**
 * 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 List<Interval> merge(List<Interval> intervals) {
         if(intervals.size() <= 1)
            return intervals;
         // Sort by ascending starting point using an anonymous Comparator
        Collections.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval i1, Interval i2) {
                return i1.start-i2.start;
            }
        });
        List<Interval> result = new LinkedList<Interval>();
        int start = intervals.get(0).start;
        int end = intervals.get(0).end;
        for(int i = 1; i < intervals.size(); i++){
            int nstart = intervals.get(i).start;
            int nend = intervals.get(i).end;
            //if not disjoint set
            if(end >= nstart){
               end = Math.max(end, nend);
           }else{
                result.add(new Interval(start,end));
                start = nstart;
                end = nend;
            }
        }
        //add the last interval
        result.add(new Interval(start, end));
        return result;
    }
}