第二十一章：数组的区间合并——合并重叠区间与插入新区间

区间合并，说白了就是处理一堆有重叠的“线段”。

我刚开始接触这类问题时，总觉得不就是比大小嘛，有什么难的？直到有一次在项目中处理用户的时间段数据，才发现坑比想象的多。嗯，今天咱们就来好好聊聊这个。

21.1 什么是区间合并？

先看一个场景：你有一组区间，比如 [1,3]、[2,6]、[8,10]、[15,18]。这些区间有的互相重叠（[1,3] 和 [2,6] 重叠了），有的没有。合并重叠区间的意思就是：把重叠的部分“捏”成一个更大的区间。

比如上面这组，合并后变成 [1,6]、[8,10]、[15,18]。

为什么会这样？因为 [1,3] 和 [2,6] 重叠了，所以合并成 [1,6]。而 [8,10] 和 [15,18] 跟谁都不重叠，保持原样。

21.2 合并重叠区间的标准做法

我个人习惯用二维数组来表示区间集合。每个区间是一个长度为2的数组，比如 intervals[0] = {1, 3}。

合并的步骤其实就三步：

1. 排序：按每个区间的起点升序排列。
2. 遍历：从第一个区间开始，逐个往后看。
3. 判断：当前区间的终点是否 >= 下一个区间的起点？如果是，就合并；否则，把当前区间存起来，换下一个。

来看代码：

#include <stdio.h>
#include <stdlib.h>

// 排序用的比较函数
int cmp(const void* a, const void* b) {
    int* intervalA = *(int**)a;
    int* intervalB = *(int**)b;
    return intervalA[0] - intervalB[0];
}

// 合并重叠区间
int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes) {
    if (intervalsSize == 0) {
        *returnSize = 0;
        return NULL;
    }

    // 第一步：排序
    qsort(intervals, intervalsSize, sizeof(int*), cmp);

    // 分配结果数组
    int** result = (int**)malloc(intervalsSize * sizeof(int*));
    *returnColumnSizes = (int*)malloc(intervalsSize * sizeof(int));

    int count = 0;
    result[count] = (int*)malloc(2 * sizeof(int));
    result[count][0] = intervals[0][0];
    result[count][1] = intervals[0][1];

    // 第二步：遍历合并
    for (int i = 1; i < intervalsSize; i++) {
        // 如果当前区间的起点 <= 上一个区间的终点，说明重叠
        if (intervals[i][0] <= result[count][1]) {
            // 合并：终点取较大值
            if (intervals[i][1] > result[count][1]) {
                result[count][1] = intervals[i][1];
            }
        } else {
            // 不重叠，新建一个区间
            count++;
            result[count] = (int*)malloc(2 * sizeof(int));
            result[count][0] = intervals[i][0];
            result[count][1] = intervals[i][1];
        }
    }

    *returnSize = count + 1;
    for (int i = 0; i < *returnSize; i++) {
        (*returnColumnSizes)[i] = 2;
    }

    return result;
}

21.3 插入新区间

插入新区间是合并问题的变种。给你一组已经不重叠的区间，再给你一个新区间，让你插进去，同时合并可能产生的重叠。

我遇到这个需求是在做排课系统的时候。课程表里已经排好了课，现在要加一节临时课，得看看跟哪些课冲突了，然后合并。

做法其实不复杂：

1. 先把新区间左边不重叠的区间全部加入结果。
2. 然后处理所有跟新区间重叠的区间，合并成一个。
3. 最后把右边不重叠的区间全部加入结果。

看代码：

int** insert(int** intervals, int intervalsSize, int* intervalsColSize,
             int* newInterval, int newIntervalSize,
             int* returnSize, int** returnColumnSizes) {

    int** result = (int**)malloc((intervalsSize + 1) * sizeof(int*));
    *returnColumnSizes = (int*)malloc((intervalsSize + 1) * sizeof(int));

    int idx = 0;
    int i = 0;

    // 第一步：加入所有在新区间左边的区间（终点 < 新区间起点）
    while (i < intervalsSize && intervals[i][1] < newInterval[0]) {
        result[idx] = (int*)malloc(2 * sizeof(int));
        result[idx][0] = intervals[i][0];
        result[idx][1] = intervals[i][1];
        (*returnColumnSizes)[idx] = 2;
        idx++;
        i++;
    }

    // 第二步：合并所有与新区间重叠的区间
    while (i < intervalsSize && intervals[i][0] <= newInterval[1]) {
        if (intervals[i][0] < newInterval[0]) {
            newInterval[0] = intervals[i][0];
        }
        if (intervals[i][1] > newInterval[1]) {
            newInterval[1] = intervals[i][1];
        }
        i++;
    }
    result[idx] = (int*)malloc(2 * sizeof(int));
    result[idx][0] = newInterval[0];
    result[idx][1] = newInterval[1];
    (*returnColumnSizes)[idx] = 2;
    idx++;

    // 第三步：加入右边剩余的区间
    while (i < intervalsSize) {
        result[idx] = (int*)malloc(2 * sizeof(int));
        result[idx][0] = intervals[i][0];
        result[idx][1] = intervals[i][1];
        (*returnColumnSizes)[idx] = 2;
        idx++;
        i++;
    }

    *returnSize = idx;
    return result;
}

21.4 两种操作的对比

操作	输入条件	核心逻辑	时间复杂度
合并重叠区间	任意区间集合	先排序，再逐个合并	O(n log n)
插入新区间	已排序且不重叠的区间集合	分三段处理：左边、重叠、右边	O(n)

你想想看，合并操作因为要排序，所以是 O(n log n)。而插入操作假设原集合已经有序，所以只需要 O(n) 遍历一遍就行。

21.5 避坑指南

我来说几个自己踩过的坑：

• 边界条件：区间 [1,2] 和 [2,3] 算不算重叠？这取决于你的定义。通常我们认为 [1,2] 和 [2,3] 是重叠的（因为 2 是公共点）。但有些场景下不算。我建议统一用「终点 >= 起点」作为重叠判断。
• 空集合：如果传入的区间数组是空的，直接返回空结果。别傻乎乎地去 malloc。
• 内存泄漏：每次 malloc 都要记得 free。我在做 LeetCode 时经常因为忘记释放内存而报错。
• 整数溢出：如果区间端点很大，比如接近 INT_MAX，做加法或比较时要小心。不过一般题目不会这么变态。

21.6 知识结构图

下面这张图帮你理清区间合并的核心逻辑：

21.7 总结

区间合并和插入，说白了就是「排序 + 遍历 + 判断重叠」这三板斧。

我个人觉得，这类问题的难点不在于算法本身，而在于边界条件的处理。你想想看，空数组、单个区间、全部重叠、完全不重叠……每种情况都得考虑到。

我在项目中用过很多次这个技巧。除了排课系统，还有日志时间段的合并、IP地址段的合并等等。掌握了这个，很多看似复杂的问题都能迎刃而解。