现在的位置: 首页 > 综合 > 正文

leetcode——Insert Interval

2018年04月12日 ⁄ 综合 ⁄ 共 2355字 ⁄ 字号 评论关闭

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

解题思路:

首先,给定的list是以start有序排列。再加入一个新的interval,则需要重新排列。

其次,排列之后,生命一个记录,按照start的顺序,往后走。遇到start则+1,遇到end则-1,直到结果为零。此时,一个区间完成。

如图:

从左往右,记录(Record)的值的变化。因此,当每次从1变成0时,记录end;从0变成1时,记录start。则start与end之间即为一个区间。

但是,如何快速查找那个数字是start,那个数字是end呢?加入我从0开始走,我首先需要判断0是不是start或end。

因此,思考一种存储结构,将所有的点(本例中,0,1,2,3....12)都存入,并且每个点都对应地表明他是start或者end的次数。然后走到每个点的时候,直接查看,直接更新记录(Record)。

至于是哪种存储结构,需要考虑:

1,数字区间是否很大。

2,如何能快速查找某个点是否是start或end。

基于以上两点,衡量空间和时间效率。

leetcode中,没有在空间上难为大家,也就是说其数字空间不是很大。因此,使用二维数组记录会更加方便,因为它提供随机访问。第二维仅仅用两个深度就行。S[a][b]:a为节点下标;b=0表示start的数目,b=1时表示end的数目。因此,S[a][b]的意义就在于,表示出a点是多少个区间的start和end。

注意事项:

往往开始的点不是0,也就是说,为了节省空间可以将节点标号记录下来,记做sub。然后将其记录进index=0的空间中。这样可以节省sub之前的所有空间。

注意如何判断一个区间的开始和结束。(使用bool锁)

排序:新加入的Interval需要以start的顺序跟原有list合并。因此从速度上讲,使用LinkedList更好,也为之后的遍历创造方便。

特例:需要考虑的特例有两种:原始List为空;list元素中有start=end的区间(这个也算)。因此不要忘了这两个情况的处理。

AC代码:

public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        int max = 0;

        if(intervals==null || intervals.size()==0){
            LinkedList<Interval> list = new LinkedList<Interval>();
            list.add(newInterval);
            return list;
        }
        LinkedList<Interval> list = new LinkedList<Interval>();
        boolean flag = false;
        for(Interval interval:intervals){
            if(newInterval.start<interval.start){
                list.add(newInterval);
                if(max<newInterval.end)
                    max = newInterval.end;
                list.add(interval);
                if(max<interval.end)
                    max = interval.end;
                flag = true;
            }
            else{
                list.add(interval);
                if(max<interval.end)
                    max = interval.end;
            }
        }
        if(!flag){
            list.add(newInterval);
            if(max<newInterval.end)
                max = newInterval.end;
        }


        int sub = list.getFirst().start;
        int total = max - sub+1;
        int[][] S = new int[total][2];
        for(Interval interval:list){
            S[interval.start-sub][0] +=1;
            S[interval.end-sub][1]-=1;
        }

        LinkedList<Interval> rst = new LinkedList<Interval>();
        int flag2 = 0;
        int start = sub;
        int end;
        boolean fuweiStart = true;
        boolean fuweiEnd = true;
        for(int i=0;i<S.length;i++){
            flag2+=S[i][0];
            if(flag2>0 && fuweiStart){
                start = i+sub;
                fuweiStart=false;
                fuweiEnd = true;
            }
            flag2+=S[i][1];

            if(flag2==0 && fuweiEnd){
                end = i+sub;
                rst.add(new Interval(start,end));
                fuweiEnd = false;
                fuweiStart = true;
            }
        }
        return rst;
    }

抱歉!评论已关闭.