[56. Merge Intervals] #leetcode

56_1012.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; }
 * }
 */
class Solution {
  // O(nlgn) O(n)
    public List<Interval> merge(List<Interval> intervals) {
        // return placeholder
        List<Interval> res = new ArrayList<>();
        
        // corner case
        if (intervals == null || intervals.size() == 0) return res;
        
        // sort List
        intervals.sort((i1, i2) -> Integer.compare(i1.start, i2.start));
        
        // loop intervals and merge
        Interval cur = null;
        for (Interval interval : intervals) {
            if (cur == null) {
                cur = new Interval(interval.start, interval.end);
            } else if (cur.end < interval.start) {
                // cur is not overlap
                res.add(cur);
                cur = new Interval(interval.start, interval.end);
            } else {
                // cur is overlap
                cur.end = Math.max(interval.end, cur.end);
            }
        } 
        
        if (cur != null) {
            res.add(cur);
        }
        
        // return
        return res;
    }
}