插入区间

题目

给出一个无重叠的按照区间起始端点排序的区间列表。在列表中插入一个新的区间,要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。http://www.lintcode.com/zh-cn/problem/insert-interval/

分析

乍看似乎不太难,但仔细想想,需要考虑的情况还蛮多的,由于区间有可能存在合并,一些原有的区间还可能因为合并而消失。还是先从简单到复杂,一点点来分析吧,包含的可能情况有:

原始数组为空

这种情况下,新的区间只要插入进去即可。

原始数组中存在一个区间

这时需要比较存在的区间(以下称为当前区间)和即将插入区间(新区间)的关系,一共可能有6种情形:

  • 新区间整个在当前区间的左侧,即newInterval.end < current.start,那么此时应当将新区间插入到左侧
  • 新区间末端位于当前区间之间,但新区间起点不在当前区间中,即newInterval.start < current.start && newInterval.end > current.start && newInterval.end < current.end
  • 新区间将当前区间包含在其中,newInterval.start <= current.start && newInterval.end >= current.end
  • 新区间被当前区间所包含,是当前区间的子集
  • 新区间起点在当前区间内,终点在当前区间外
  • 新区间整个在当前区间右侧

上述的6种情况,实际处理时,又可以分成3种:

  • 新区间完全在当前区间左侧,此时只需要将新区间插入结果数组头部
  • 新区间完全在当前区间右侧,此时只需要将新区间插入结果数组尾部
  • 新区间与当前区间有交集,此时直接更新当前节点的左右边界,使其边界更新

包含更多元素的情况

当原始数组超过1个时,其实我们只需要考虑和新区间有交集的区间,其他区间不会受到影响。根据新区间的端点,可以找出所有与新区间有非空子集的区间。

如果找不到任何一个符合条件的区间,说明新区间应当直接插入到结果数组中。
如果找到了一些符合条件的区间,则逐一考察它们(此时只会出现区间被新区间包含,或者左右有交集的情况):

  • 若被新节点包含,直接删除
  • 若其左侧与新区间有交集,则将其左侧结果扩展
  • 若右侧与新区间有交集,则向右扩展
  • 由于有可能出现所有区间都被包含的情况,可以先将第一个有交集的元素取出,并更新其边界

代码实现


/**
 * Definition of Interval:
 * public classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 */

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 < Interval > insert(ArrayList < Interval> intervals, Interval newInterval) {        
        if(intervals == null){
            intervals = new ArrayList< Interval >();
        }
        
        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.start < current.start ? newInterval.start:current.start;
                current.end = newInterval.end > current.end?newInterval.end:current.end;
            }
            return intervals;
        }
        
        Interval temp;
        List< Item > result = new ArrayList();
        for(int i=0; i<intervals.size(); i++){
            temp = intervals.get(i);
            int type = type(temp, newInterval);
            if(type>-1){
                result.add(new Item(temp, type));
            }
        }
        
        if(result.size() == 0){
            Interval current, next;
            for(int i=0; i<intervals.size()-1; i++){
                current = intervals.get(i);
                next = intervals.get(i+1);
                if(newInterval.end < current.start){
                    intervals.add(i, newInterval);
                    return intervals;
                }else if(newInterval.start > current.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 < result.size(); ){
                Item item = result.get(i);
                switch(type(item.interval, first)){
                    case -1:
                    case -100:
                    case 0:
                        i++;
                        break;
                    case 1:
                        first.end = item.interval.end;
                        intervals.remove(item.interval);
                        result.remove(i);
                        break;
                    case 3:
                        intervals.remove(item.interval);
                        result.remove(i);
                        break;
                }
            }
            
        }
        return intervals;
    }
};
Show Comments

Get the latest posts delivered right to your inbox.