合并区间

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;

}