合并数组区间（合并数组区间怎么求）



写在前面

老粉丝可能知道现阶段的LeetCode刷题将按照某一个特定的专题进行，之前的【贪心算法】已经结束，虽然只有三个题却包含了简单，中等，困难这三个维度，今天介绍的是第二个专题【数组】

数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。在每一种编程语言中，基本都会有数组这种数据类型。不过，它不仅仅是一种编程语言中的数据类型，还是一种最基础的数据结构。

贪心算法回顾：

【LeetCode】贪心算法--买卖股票的最佳时机II（122）

【LeetCode】贪心算法--划分字母区间（763）

【LeetCode】贪心算法--分发糖果（135）

刷题汇总：

【LeetCode】汇总贴（NO.1-20）

今日题目

给出一个区间的集合，请合并所有重叠区间。

示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

题目分析

先将目标区间数组从小到大排序，然后从第一个区间开始，如果相邻的两个区间，end小于start则合并区间，且生成新的区间，如果不小于，则放到返回区间，可以看下面几个例子。

[1,3][2,6] ->[1,6]

第一个区间的end大于等于第二个区间的start,同时第二个区间的end大于第一个区间的end。

[2,8][3,5] ->[2,8]

第一个区间的end大于等于第二个区间的start,同时第二个区间的end小于第一个区间的end。

[1,2][3,4] -> [1,2][3,4]

第一个区间的end小于第二个区间的start 。

代码实现

【推荐阅读】

【LeetCode】贪心算法--划分字母区间（763）

python异常报错详解

机器学习实战--住房月租金预测（3）

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/bcyy/50804.html