合并区间
NC37 合并区间
- 题目
- 题解(219)
- 讨论(302)
- 排行
- 面经new
中等 通过率:24.90% 时间限制:2秒 空间限制:256M
描述
给出一组区间,请合并所有重叠的区间。
请保证合并后的区间按区间起点升序排列。
数据范围:区间组数 0≤𝑛≤2×1050≤n≤2×105,区间内 的值都满足 0≤𝑣𝑎𝑙≤2×1050≤val≤2×105
要求:空间复杂度 𝑂(𝑛)O(n),时间复杂度 𝑂(𝑛𝑙𝑜𝑔𝑛)O(nlogn)
进阶:空间复杂度 𝑂(𝑣𝑎𝑙)O(val),时间复杂度𝑂(𝑣𝑎𝑙)O(val)
示例1
输入:
[[10,30],[20,60],[80,100],[150,180]]
返回值:
[[10,60],[80,100],[150,180]]
/**
- struct Interval {
- int start;
- int end;
- };/ /*
- 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
- @param intervals Interval类一维数组
- @param intervalsLen int intervals数组长度
- @return Interval类一维数组
- @return int* returnSize 返回数组行数/ void sort(struct Interval intervals, int intervalsLen) {int i, j;printf("%d ",666);for ( i = 0; i < intervalsLen - 1; i++) {for ( j = i + 1; j < intervalsLen; j++) {struct Interval n;if (intervals[i].start > intervals[j].start) {n.start = intervals[i].start;intervals[i].start = intervals[j].start;intervals[j].start = n.start;}
}struct Interval* merge(struct Interval* intervals, int intervalsLen,int* returnSize ) {// write code hereif (intervals == NULL || intervalsLen == 0) {return NULL;}if (intervalsLen == 1) {* returnSize = 1;return intervals;}
sort( intervals, intervalsLen); //printf("%d %d\n", a[1].start, a[1].end); int i; * returnSize = 0; struct Interval* b = (struct Interval*)malloc(sizeof(struct Interval) * intervalsLen); for ( i = 0; i < intervalsLen - 1; i++) { if (intervals[i].end >= intervals[i + 1].start) { printf("%d %d\n", intervals[i].start, intervals[i].end); intervals[i + 1].start = intervals[i].start; if (intervals[i].end >= intervals[i + 1].end) { intervals[i + 1].end = intervals[i].end; } } else { b[(* returnSize)].start = intervals[i].start; b[(* returnSize)].end = intervals[i].end; (* returnSize)++; } } b[(* returnSize)].start = intervals[i].start; b[(* returnSize)].end = intervals[i].end; (* returnSize)++; return b;
}