57. Insert Interval

description

有一些在x轴上的线段，合并这些线段
有一些在x轴上的线段，这些线段两两之间没有交集，再给定一个线段，返回合并后线段集合

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].

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

思路与解法

第一道题首先是排序，对排好的线段进行遍历

class Interval {
    int start;
    int end;
    Interval() { start = 0; end = 0; }
    Interval(int s, int e) { start = s; end = e; }
}

public List<Interval> merge(List<Interval> intervals) {
    Collections.sort(intervals, new Comparator<Interval>() {
        @Override
        public int compare(Interval o1, Interval o2) {
            if(o1.start>o2.start)return 1;
            else if(o1.start==o2.start)return 0;
            else return -1;
        }
    });
    List<Interval> list=new ArrayList<>();
    int start,end,i;
    i=0;
    while (i<intervals.size()){
        Interval interval=intervals.get(i);
        start=interval.start;
        end=interval.end;
        while (i+1<intervals.size()&&end>=intervals.get(i+1).start){
            interval=intervals.get(i+1);
            if(end<interval.end)end=interval.end;
            i++;
        }
        list.add(new Interval(start,end));
        i++;
    }
    return list;
}

第二道题分下面几种情况：
newInterval在intervals的最前面
newInterval在intervals的最后面
newInterval既不在最前面，也不在最后面，而且不与intervals中的任何线段相交
newInterval与intervals中的线段相交

public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
    if(intervals==null){
        List<Interval> list=new ArrayList<>();
        list.add(newInterval);
        return intervals;
    }
    if (intervals.size()==0) {
        intervals.add(newInterval);
        return intervals;
    }
    for(int i=0;i<intervals.size();i++){
        Interval interval=intervals.get(i);
        if(i==0&&newInterval.end<interval.start){
            intervals.add(0,newInterval);
            return intervals;
        }else if(i==intervals.size()-1&&interval.end<newInterval.start){
            intervals.add(newInterval);
            return intervals;
        }else if(interval.end<newInterval.start&&intervals.get(i+1).start>newInterval.end){
            intervals.add(i+1,newInterval);
            return intervals;
        } else {
            if(interval.end>=newInterval.start){
                newInterval.start=Math.min(newInterval.start,interval.start);
                newInterval.end=Math.max(newInterval.end,interval.end);
                intervals.remove(i);
                while (i<intervals.size()&&newInterval.end>=intervals.get(i).start){
                    newInterval.end=Math.max(newInterval.end,intervals.get(i).end);
                    intervals.remove(i);
                }
                if(i==intervals.size())intervals.add(newInterval);
                else intervals.add(i,newInterval);
                return intervals;
            }
        }
    }
    return intervals;
}