首页 > 其他 > 详细

56. Merge Intervals

时间:2016-05-08 11:38:19      阅读:165      评论:0      收藏:0      [点我收藏+]
    /*
     * 56. Merge Intervals 
     * 2016-5-7 by Mingyang 
     * 直接比较就好了,不要分的太细
     * 开始想分三类,一类是加prev,一类是merge,另一类是prev包含了cur
     * 现在简化了,2,3合在一起了,都merge
     * 另外就是注意如何写comparator
     */
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals == null || intervals.size() <= 1)
            return intervals;
        // sort intervals by using self-defined Comparator,
        // Collections.sort有两种方法,这种需要comparator,所以自己在后面定义了一个
        Collections.sort(intervals, new IntervalComparator());
        List<Interval> result = new ArrayList<Interval>();
        Interval prev = intervals.get(0);
        for (int i = 1; i < intervals.size(); i++) {
            Interval curr = intervals.get(i);
            if (prev.end >= curr.start) {
                // merged case
                Interval merged = new Interval(prev.start, Math.max(prev.end,
                        curr.end));
                prev = merged;
            } else {
                result.add(prev);
                prev = curr;
            }
        }
        result.add(prev);
        return result;
    }
}
   class IntervalComparator implements Comparator<Interval> {
    public int compare(Interval i1, Interval i2) {
        return i1.start - i2.start;
    }    

 

56. Merge Intervals

原文:http://www.cnblogs.com/zmyvszk/p/5469981.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!