编程题 69 /104

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

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

//"区间"定义
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：对所有区间按左端点排序，然后遍历时维护右端点最大值即可。

解法2：对值域差分后做前缀和，然后遍历一遍值域即可得到所有区间。

查看讨论

上一题下一题

扫一扫，把题目装进口袋