题目

给出若干闭合区间，合并所有重叠的部分。
http://www.lintcode.com/zh-cn/problem/merge-intervals/

分析

这题目看着很眼熟，之前有一道很类似的题目——插入区间（http://www.lintcode.com/zh-cn/problem/insert-interval/ ）。显然只要把插入区间的代码借用过来，这道题目就搞定了，关于插入区间，解析可以参考https://www.hoyt-tian.com/cha-ru-qu-jian/

代码

class Item{
    Interval interval;
    int type = -1;
    Item(Interval it, int type){
        this.interval = it;
        this.type = type;
    }
}

public class Solution {
        int type(Interval current, Interval target){
        if(current.start > target.end){
            return -1; // 
        }else if(target.end>=current.start && target.end<=current.end && current.start>target.start){
            return 1; // left extend
        }else if(target.start < current.start && target.end > current.end){
            return 3; // contain
        }else if(target.start>= current.start && target.end <= current.end){
            return 0; // included
        }else if(target.start>=current.start && target.start<= current.end){
            return 2; // right extend;
        }else if(target.start > current.end){
            return -2; // 
        }
        return -100;
    }
    /*
     * @param intervals: Sorted interval list.
     * @param newInterval: new interval.
     * @return: A new interval list.
     */
    public ArrayList insert(ArrayList intervals, Interval newInterval) {
        // write your code here
        
        if(intervals == null){
            intervals = new ArrayList();
        }
        
        if(intervals.size() == 0){
            intervals.add(newInterval);
            return intervals;
        }else if(intervals.size() == 1){
            Interval current = intervals.get(0);
            if(current.start > newInterval.end){
                intervals.add(0, newInterval);
            } 
            else if(current.end < newInterval.start){ 
                intervals.add(newInterval);
            }
            else{
                current.start = newInterval.startcurrent.end?newInterval.end:current.end;
            }
            return intervals;
        }
        
        Interval temp;
        List result = new ArrayList();
        for(int i=0; i-1){
                result.add(new Item(temp, type));
            }
        }
        
        if(result.size() == 0){
            Interval current, next;
            for(int i=0; icurrent.end && newInterval.end < next.start){
                    intervals.add(i+1, newInterval);
                    return intervals;
                }
            }
            intervals.add(newInterval);
            return intervals;
        }else{
            
            Interval first = result.get(0).interval;
            if(newInterval.start < first.start){
                first.start = newInterval.start;
            }
            if(newInterval.end > first.end){
                first.end = newInterval.end;
            }
            
            
            for(int i=1; i merge(List intervals) {
        // write your code here
        ArrayList result = new ArrayList<>();
        if(intervals == null || intervals.size() < 1) return result;
        
        result.add(intervals.get(0));
        for(int i=1; i < intervals.size(); i++){
            result = insert(result, intervals.get(i));
        }
        return (List)result;
    }
}