贪心算法:合并区间

贪心算法:合并区间

码农世界 2024-05-24 前端 68 次浏览 0个评论

参考资料:代码随想录

题目链接:. - 力扣(LeetCode)

做过用最少数量的箭引爆气球和无重叠区间这两道题目后,题意和题解都不难理解。唯一的一点儿难点是对于api的运用。

class Solution {
    public int[][] merge(int[][] intervals) {
        if(intervals.length == 0) return null;
        Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));
        //List res = new ArrayList<>();
        List res = new LinkedList<>();
        //默认有一个区间
        res.add(intervals[0]);
        //遍历区间
        for(int i = 1;i < intervals.length;i++){
            //判断是否是重复区间
            if(intervals[i][0] <= res.getLast()[1]){
                //进行合并操作
                int begin = res.get(i-1)[0];
                int end = Math.max(intervals[i][1],res.get(i-1)[1]);
                res.removeLast();
                res.add(new int[]{begin,end});
            }else{
                //不重复则直接放入
                res.add(intervals[i]);
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}

转载请注明来自码农世界,本文标题:《贪心算法:合并区间》

百度分享代码,如果开启HTTPS请参考李洋个人博客
每一天,每一秒,你所做的决定都会改变你的人生!

发表评论

快捷回复:

评论列表 (暂无评论,68人围观)参与讨论

还没有评论,来说两句吧...

Top