Interval Problems

Algorithm

关于interval数组结构的操作，在面试中也是一种比较常见的数据结构.

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

此类题型 需要注意时间空间复杂度说明。
1. Merge Intervals
假设这些interval是有序的（也就是说先按起始点排序，然后如果起始点相同就按结束点排序），那么要把它们合并就只需要按顺序读过来，如果当前一个和结果集中最后一个有重叠，那么就把结果集中最后一个元素设为当前元素的结束点（不用改变起始点因为起始点有序，因为结果集中最后一个元素起始点已经比当前元素小了）。那么剩下的问题就是如何给interval排序，在java实现中就是要给interval自定义一个Comparator，规则是按起始点排序，然后如果起始点相同就按结束点排序。

public List<Interval> merge(List<Interval> intervals) {
        // notice this intervals list is not sorted!!
        /**整个算法是先排序，然后再做一次线性遍历，时间复杂度是O(nlogn+n)=O(nlogn)，空间复杂度是O(1)，因为不需要额外空间，只有结果集的空间。**/
         List<Interval> res = new ArrayList<Interval>();
         if(intervals==null||intervals.size()==0)
             return res;
         Collections.sort(intervals, new Comparator<Interval>() {
             @Override
            public int compare(Interval o1, Interval o2) {
                return Integer.compare(o1.start, o2.start);
            }
        });
         res.add(intervals.get(0));
         for(int i=1;i<intervals.size();i++){
             int start = res.get(res.size()-1).start;
             int end = res.get(res.size()-1).end;
             if(intervals.get(i).start>end){
                 res.add(intervals.get(i));
             }else if(intervals.get(i).end<start){
                 res.add(res.size()-1,intervals.get(i));
             }else{
                 start = Math.min(start, intervals.get(i).start);
                 end = Math.max(end, intervals.get(i).end);
                 res.set(res.size()-1, new Interval(start,end));
             }
         }
         return res;
    }

1. Insert Intervals
   这道题不需要排序，因为插入之前已经默认这些intervals排好序了。简单一些的是这里最多只有一个连续串出现冲突，因为就插入那么一个。基本思路就是先扫描走到新的interval应该插入的位置，接下来就是插入新的interval并检查后面是否冲突，一直到新的interval的end小于下一个interval的start，然后取新interval和当前interval中end大的即可。因为要进行一次线性扫描，所以时间复杂度是O(n)。而空间上如果我们重新创建一个ArrayList返回，那么就是O(n)。(为什么不in-place的进行操作，这样就不需要额外空间，但是如果使用ArrayList这个数据结构，那么删除操作是线性的，如此时间就不是O(n)的。如果这道题是用LinkedList那么是可以做到in-place的，并且时间是线性的。)

public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
         List<Interval> res = new ArrayList<Interval>();
            res.add(newInterval);
         if(intervals==null)
             return res;
         for(Interval interval:intervals){
             int start = res.get(res.size()-1).start;
             int end = res.get(res.size()-1).end;
             if(start>interval.end)
                 res.add(res.size()-1, interval);
             else if(end<interval.start)
                 res.add(interval);
             else{
                 start = Math.min(start, interval.start);
                 end = Math.max(end, interval.end);
                 res.set(res.size()-1, new Interval(start, end));
             }
         }
         return res;
     }