2023年12月5日，每天花费一分钟，用C语言实现两个区间的合并

往期回顾

2023年12月3日，每天花费一分钟，坚持练习C语言

2023年12月4日，每天花费一分钟，用C语言计算企业奖金提成？

每日一练

/ Daily Exercises

合并区间：

以数组 intervals 表示若千个间的集合，其中单个区间为 intervals[i] = [starti，endi]。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组票恰好覆盖输入中的所有区间。

1

题目分析

题目的目的是将一个区间数组合并成一个不重叠的区间数组，这个区间数组可以恰好覆盖输入中的所有区间。

输入一个二维数组，每个元素是一个长度为2的一维数组，表示一个区间的起点和终点。

输出也是一个二维数组，每个元素是一个长度为2的一维数组，表示一个合并后的区间的起点和终点。

输入的区间个数、起点和终点的范围。

示例 1: 输入: intervals = [[1,3],[2,6],[8,10],[15,18

输出:[[1,6],[8,10],[15,18]] 解释:区间 [1,3] 和 [2,6] 重叠，将它们合并

难点是如何判断两个区间是否重叠，以及如何合并重叠的区间。

2

程序展示

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


// 定义一个结构体，表示一个区间
typedef struct Interval 
{
    int start; // 区间的起点
    int end; // 区间的终点
} Interval;


// 定义一个比较函数，用于对区间按照起点升序排序
int compare(const void *a, const void *b) 
{
    Interval *i1 = (Interval *)a;
    Interval *i2 = (Interval *)b;
    return i1->start - i2->start;
}


// 定义一个函数，用于合并区间数组
Interval *merge(Interval *intervals, int intervalsSize, int *returnSize) 
{
    // 如果区间数组为空或者只有一个区间，直接返回
    if (intervalsSize == 0 || intervalsSize == 1) 
    {
        *returnSize = intervalsSize;
        return intervals;
    }
    // 对区间数组按照起点升序排序
    qsort(intervals, intervalsSize, sizeof(Interval), compare);
    // 创建一个新的区间数组，用于存放合并后的区间
    Interval *merged = (Interval *)malloc(sizeof(Interval) * intervalsSize);
    // 初始化合并后的区间个数为0
    *returnSize = 0;
    // 遍历排序后的区间数组
    for (int i = 0; i < intervalsSize; i++) 
    {
        // 如果合并后的区间数组为空，或者当前区间的起点大于合并后的区间数组的最后一个区间的终点，说明当前区间和合并后的区间数组不重叠，直接将当前区间加入合并后的区间数组
        if (*returnSize == 0 || intervals[i].start > merged[*returnSize - 1].end) 
        {
            merged[*returnSize] = intervals[i];
            (*returnSize)++;
        } 
        else 
        {
            // 否则，说明当前区间和合并后的区间数组的最后一个区间重叠，将合并后的区间数组的最后一个区间的终点更新为当前区间和合并后的区间数组的最后一个区间的终点的较大值
            merged[*returnSize - 1].end = intervals[i].end > merged[*returnSize - 1].end ? intervals[i].end : merged[*returnSize - 1].end;
        }
    }
    // 返回合并后的区间数组
    return merged;
}


// 定义一个函数，用于打印区间数组
void printIntervals(Interval *intervals, int intervalsSize) 
{
    printf("[");
    for (int i = 0; i < intervalsSize; i++) 
    {
        printf("[%d, %d]", intervals[i].start, intervals[i].end);
        if (i < intervalsSize - 1) 
        {
            printf(", ");
        }
    }
    printf("]\n");
}


// 定义一个主函数，用于测试
int main() 
{
    // 创建一个测试用的区间数组
    Interval intervals[] = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
    // 获取区间数组的大小
    int intervalsSize = sizeof(intervals) / sizeof(intervals[0]);
    // 打印区间数组
    printf("输入的区间数组是：\n");
    printIntervals(intervals, intervalsSize);
    // 调用合并函数，获取合并后的区间数组和大小
    int returnSize;
    Interval *merged = merge(intervals, intervalsSize, &returnSize);
    // 打印合并后的区间数组
    printf("合并后的区间数组是：\n");
    printIntervals(merged, returnSize);
    // 释放合并后的区间数组的内存
    free(merged);
    // 返回0，表示程序正常结束
    return 0;
}

3

效果展示

#挑战30天在头条写日记#