我要招人

去企业版

首页 > 试题广场 >

合并区间

[编程题]合并区间

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

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

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

数据范围：区间组数 $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 展开全文

王清楚

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

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

我和我

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

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

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, 则合并不了。总共只有以上这两种情况。所以对于上面，我们可以将展开全文

小洋芋热爱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 展开全文

Zengwenxx

发表于 2021-12-15 11:14:48

# class Interval: # def __init__(self, a=0, b=0): # self.start = a # self.end = 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 展开全文

牛客100868151号

发表于 2022-07-04 18:21:50

见注释 function merge(intervals) { // 按区间的左端点从小到大排序 intervals.sort((a, b) => a.start -&nb 展开全文

大厂算法岗必拿下

发表于 2021-09-15 04:35:42

首先对区间首端点从小到大进行排序。然后如果开始端点相同，end按照降序排列脑子中画出这些排序的区间，由底到高画。一共就分为3中情况，最后一种覆盖又分为起始点不同的覆盖，以及起始点相同的覆盖。对于延长区间只有一种情况，就是第二段的end比最后一段end长，这时候直接更新已有end就行。 /** 展开全文

问题信息

数组排序

难度：

302条回答 1214收藏 26107浏览

通过挑战的用户

查看代码

躺平仔躺不平

2023-03-10 13:59:15
老法日尔

2023-03-05 20:02:11
牛客79923...

2023-03-04 16:26:47
😭呜呜

2023-02-26 10:59:27
滑水

2023-02-24 20:59:27

合并区间

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题