2021/2/1 合并区间

合并区间

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

题目描述

给出一组区间,请合并所有重叠的区间。

示例

输入

[[10,30],[20,60],[80,100],[150,180]]

返回值

[[10,60],[80,100],[150,180]]

解题思路

  1. 按照 start 值从小到大排序
  2. 遍历所有元素,后一个元素的 start 比前一个的 end 还要小,则比较后一个的 end 和前一个的 end 哪个更大,最大的那个 end 值赋给前一个元素的 end,并删除后一个元素。

王清楚大大的博客《【牛客题霸题解】合并区间》 已经给出了很生动形象的思路,在这里偶就不多卖弄了,不过有一个点需要注意:
图片说明
这时候 20 小于 50,不能用 20 去替换前一个的 end。

Java代码实现

public class Solution {
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        if (intervals == null || intervals.size() < 2) return intervals;
        // 排序,start 值从小到大;start 值相同则按照 end 从小到大排序
        Collections.sort(intervals, new Comparator<Interval>() {
            public int compare (Interval o1, Interval o2) {
                if (o1.start == o2.start) {
                    return o1.end - o2.end;
                } else {
                    return o1.start - o2.start;
                }
            }
        });

        // 获得 intervals 的迭代器,对 intervals 本身进行操作
        Iterator<Interval> it = intervals.iterator();
        Interval prev = it.next();
        while (it.hasNext()) {
            Interval current = it.next();
            // 若遍历到的 start 比前一个的 end 小
            if (current.start <= prev.end) {
                // 前一个元素的 end 赋最大那一个值
                prev.end = prev.end > current.end ? prev.end : current.end;
                it.remove();
            } else {
                prev = current;
            }
        }
        return intervals;
    }
}
全部评论

相关推荐

07-14 13:37
重庆大学 C++
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-10 14:10
啊啊啊啊好幸福,妈妈是我找工作发疯前的一束光
黑皮白袜臭脚体育生:看了这篇帖子之后已经第一百次质问老妈,仍然没有得到我的老妈是老板的回答
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务