题解 | #合并区间#

合并区间

http://www.nowcoder.com/practice/69f4e5b7ad284a478777cb2a17fb5e6a

思路:先按区间左边界按升序排序,用Collections.sort();
1.设置双指针,一个指向当前已合并过的末尾的区间p,一个指向还未合并过的第一个区间q。
2.比较q的start值与p的end值的大小
1)若q.start<=p.end,取p.end与q.end的最大值赋给p.end,并删除q。删除后就相当于进行了q++,因此不需要额外的q++了。
2)若q.start>p.end,说明不重合。p++,q++。

public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        Collections.sort(intervals,new Comparator<Interval>(){
            @Override
            public int compare(Interval o1,Interval o2){
                return o1.start-o2.start;
            }
        });
        int p=0;
        int q=1;
        while(q<intervals.size()){
            Interval ip=intervals.get(p);
            Interval iq=intervals.get(q);
            if(iq.start<=ip.end){
                ip.end=Math.max(iq.end,ip.end);
                intervals.remove(q);
            }else{
                p++;
                q++;
            }
        }
        return intervals;
    }
全部评论

相关推荐

三年之期已到我的offer快到碗里来:9硕都比不上9本
点赞 评论 收藏
分享
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务