题解 | #插入区间#

这个题看起来可以使用“合并区间”的解法，但题目已经告知了输入的数组是已经按start字段升序，那么我们仅需要找到插入点，然后向后合并即可。时间复杂度O(n)，空间复杂度O(n)(采用了list)。

public class Solution {
    public Interval[] insertInterval (Interval[] Intervals, Interval newInterval) {
        List<Interval> list = new LinkedList<>();
        boolean flag = false;//判断目标区间是否已经成功加入
        for(int i=0;i<Intervals.length;++i){
            list.add(Intervals[i]);
        }
        for(int i=0;i<list.size();++i){
            if(list.get(i).start>newInterval.start){
                list.add(i,newInterval);
                flag = true;
                break;
            }
        }
        if(!flag)list.add(newInterval);//如果目标区间还没加入，直接放到最后
        List<Interval> reslist = new LinkedList<>();
        reslist.add(list.get(0));
        for(int i=1;i<list.size();++i){
            if(list.get(i).start>reslist.get(reslist.size()-1).end){
                reslist.add(list.get(i));
            }
            else {
                reslist.get(reslist.size()-1).end = Math.max(list.get(i).end,reslist.get(reslist.size()-1).end);
            }
        }
        Interval[] res = new Interval[reslist.size()];
        int index = 0;
        for(Interval i:reslist){
            res[index++] = i;
        }
        return res;
    }
}