Insert Interval -- LeetCode

原题链接: http://oj.leetcode.com/problems/insert-interval/
这道题跟Merge Intervals很类似，都是关于数据结构interval的操作。事实上，Merge Intervals是这道题的子操作，就是插入一个interval，如果出现冲突了，就进行merge。跟Merge 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 ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
    ArrayList<Interval> res = new ArrayList<Interval>();
    if(intervals.size()==0)
    {
        res.add(newInterval);
        return res;
    }
    int i=0;
    while(i<intervals.size() && intervals.get(i).end<newInterval.start)
    {
        res.add(intervals.get(i));
        i++;
    }
    if(i<intervals.size())
        newInterval.start = Math.min(newInterval.start, intervals.get(i).start);
    res.add(newInterval);
    while(i<intervals.size() && intervals.get(i).start<=newInterval.end)
    {
        newInterval.end = Math.max(newInterval.end, intervals.get(i).end);
        i++;
    }
    while(i<intervals.size())
    {
        res.add(intervals.get(i));
        i++;
    }
    return res;
}

这道题有一个变体，就是如果插入的时候发现冲突，那就返回失败，不插入了。看起来好像比上面这道题还要简单，但是要注意的是，如此我们就不需要进行线性扫描了，而是进行二分查找，如果不冲突，则进行插入，否则直接返回失败。这样时间复杂度可以降低到O(logn)。当然这里需要用二分查找树去维护这些intervals。所以一点点变化可能可以使复杂度降低，还是应该多做思考哈。
同时，这种题目还可以问一些关于OO设计的东西，比如就直接问你要实现一个intervals的类，要维护哪些变量，实现哪些功能，用什么数据结构，等等。这些你可以跟面试官讨论，然后根据他的功能要求用相应的数据结构。所以扩展性还是很强的，大家可以考虑的深入一些。