我要招人

去企业版

首页 > 试题广场 >

合并区间

[编程题]合并区间

热度指数：169702 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

请保证合并后的区间按区间起点升序排列。

//"区间"定义
class Interval {
   int start; //起点
   int end;   //终点
}

数据范围：区间组数 $0 \le n \le 2 \times 10^5$ ，区间内的值都满足 $0 \le val \le 2 \times 10^5$

要求：空间复杂度 $O(n)$ ，时间复杂度 $O(nlogn)$

进阶：空间复杂度 $O(val)$ ，时间复杂度 $O(val)$

示例1

输入

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

输出

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

示例2

输入

[[0,10],[10,20]]

输出

[[0,20]]

算法知识视频讲解

牛客题解官

发表于 2022-04-22 13:02:03

精华题解题目主要信息: 给出一组区间，区间包括起始点，要求将重叠的区间合并重叠后的区间按照起点位置升序排列举一反三：学习完本题的思路你可以解决如下题目： BM95. 分糖果问题 BM96. 主持人调度方法: 排序+贪心(推荐使用) 知识点：贪心思想贪心思想属于动态规划思想中的一种，其基本原理是展开全文

未来0116

发表于 2021-07-10 13:17:57

精华题解一.题目描述NC37合并区间:题目链接：https://www.nowcoder.com/practice/69f4e5b7ad284a478777cb2a17fb5e6atpId=196&&tqId=37071&rp=1&ru=/activity/oj&qr 展开全文

蒙牛麦片

发表于 2021-07-16 22:08:53

精华题解 NC37 合并区间题意分析：将所给的多个区间，将重叠的区间的进行合并。题解一（贪心）：如有区间如下： [[10,30],[20,60],[80,100],[150,180]]合并的结果为： [[10,60],[80,100],[150,180]]区间[10，30]和区间[20，60]有重叠的展开全文

包子君Y

发表于 2020-09-11 15:39:39

对左边界排序，如果下一个区间的左边界在前一个的有边界内，考虑是否要更新边界，如果如果下一个区间的左边界在前一个的有边界外，说明区间无法合并，开始计算下一个区间 public ArrayList<Interval> merge(ArrayList<Interval> i 展开全文

我和我

发表于 2021-12-09 22:29:05

/** * Definition for an interval. * public class Interval { * int start; * int end; * Interval() { start = 0; end = 0; } * Inter 展开全文

王清楚

发表于 2020-12-31 15:33:58

首先我们来考虑一个问题：什么样的两个区间可以合并？像上图这样，起点大的那个区间（[13，16]）的起点在另一个区间的范围之内，这样两个区间就可以进行合并了所以我们把全部的区间按起点进行排序，然后看一下第i个区间能不能和i-1个区间合并，如果能合并的话，就删掉第i-1个区间，然后把第i个区间变成这两展开全文

LaN666

发表于 2021-03-02 23:49:13

NC 37 合并区间方法一：排序+双指针对于两个区间[a,b] [c,d] 1、若 a < c < b,则这两个区间可合并，此时若b>d,则合并后的区间为[a,b],反之为[a,d] 2、若 c > b, 则合并不了。总共只有以上这两种情况。所以对于上面，我们可以将展开全文

东厂的事我管不了

发表于 2022-05-30 12:08:57

比较简洁易懂的写法，没申请新的空间。 int cmp(const void *a, const void *b) { return (((struct Interval*)a)->start - ((struct Interval*)b)->start); } struct 展开全文

小洋芋热爱NLP

发表于 2020-12-14 21:48:20

- 1、题目描述： - 2、题目链接：https://www.nowcoder.com/practice/69f4e5b7ad284a478777cb2a17fb5e6a?tpId=117&&tqId=34958&rp=1&ru=/ta/job-code-high&a 展开全文

下辈子不想用脑子了

发表于 2022-01-12 11:41:01

class Interval: def init(self, a=0, b=0): self.start = a self.end = b 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 @param intervals Interval类一维数组 @return I 展开全文