757. 设置交集大小至少为2（力扣）

一个整数区间 [a, b]  ( a < b ) 代表着从 a 到 b 的所有连续整数，包括 a 和 b。

给你一组整数区间intervals，请找到一个最小的集合 S，使得 S 里的元素与区间intervals中的每一个整数区间都至少有2个元素相交。

输出这个最小集合S的大小。

示例 1:

输入: intervals = [[1, 3], [1, 4], [2, 5], [3, 5]]
输出: 3
解释:
考虑集合 S = {2, 3, 4}. S与intervals中的四个区间都有至少2个相交的元素。
且这是S最小的情况，故我们输出3。

示例 2:

输入: intervals = [[1, 2], [2, 3], [2, 4], [4, 5]]
输出: 5
解释:
最小的集合S = {1, 2, 3, 4, 5}.

C语言代码展示

static void help(int** intervals, int** temp, int *colSize, int pos, int num) {
    for (int i = pos; i >= 0; i --) {
        if (intervals[i][1] < num) {  //如果当前集合和前一集合没有交集，则退出循环
            break;
        }
        temp[i][colSize[i]++] = num;  //如果有交集，让有交集的集合+1，并将数存入temp
    }
}

static inline int cmp(const void* pa, const void* pb) {
    if ((*(int **)pa)[0] == (*(int **)pb)[0]) {
        return (*(int **)pb)[1] - (*(int **)pa)[1];  //左边界相等，则右边界降序排列
    }
    return (*(int **)pa)[0] - (*(int **)pb)[0];  //左边界升序排列
}

int intersectionSizeTwo(int** intervals, int intervalsSize, int* intervalsColSize){
    int res = 0;
    int m = 2;
    qsort(intervals, intervalsSize, sizeof(int *), cmp);  //左边界升序，右边界降序
    int **temp = (int **)malloc(sizeof(int *) * intervalsSize);
    for (int i = 0; i < intervalsSize; i++) {
        temp[i] = (int *)malloc(sizeof(int) * 2);
    }
    int *colSize = (int *)malloc(sizeof(int) * intervalsSize);
    memset(colSize, 0, sizeof(int) * intervalsSize);
    for (int i = intervalsSize - 1; i >= 0; i --) {  //遍历所有集合，为所有集合都找到两个与其他集合有交集的数
        for (int j = intervals[i][0], k = colSize[i]; k < m; j++, k++) {
            res++;
            help(intervals, temp, colSize, i - 1, j);
        }
    }
    for (int i = 0; i < intervalsSize; i++) {
        free(temp[i]);
    }
    free(colSize);
    return res;
}