排序法区间合并

合并区间

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

public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        // 根据左边界升序排列,左边界相等时根据右边界升序排列
        Collections.sort(intervals, (a, b) -> {
            if (a.start == b.start) return a.end - b.end;
            else return a.start - b.start;
        });
        int size = intervals.size();
        ArrayList<Interval> res = new ArrayList<>();
        for (int i = 1; i <= size; i++) {
            int start = intervals.get(i-1).start;
            int maxEnd = intervals.get(i-1).end;
            // 当合并区间左边界>=i的左边界时,更新合并区间的左边界,否则退出循环
            while (i<size && maxEnd >= intervals.get(i).start) {
                maxEnd = Math.max(maxEnd, intervals.get(i).end);
                i++;
            }
            // 登记区间
            res.add(new Interval(start, maxEnd));
        }
        return res;
    }

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-11-30 15:59
东北大学_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
01-12 12:42
点赞 评论 收藏
转发
头像
2022-12-02 15:29
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议