题解 | 合并区间

/**
 * struct Interval {
 *	int start;
 *	int end;
 * };
 */
#include <stdlib.h>
int compare(const void* a, const void* b)
{
    
    struct Interval* intervalA = (struct Interval*)a;
    struct Interval* intervalB = (struct Interval*)b;

    return intervalA->start - intervalB->start; 
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param intervals Interval类一维数组 
 * @param intervalsLen int intervals数组长度
 * @return Interval类一维数组
 * @return int* returnSize 返回数组行数
 */
struct Interval* merge(struct Interval* intervals, int intervalsLen, int* returnSize ) 
{
    // write code here
    if(intervalsLen <= 1)//如果区间为0，1。直接返回原数组
    {
        *returnSize = intervalsLen;
        return intervals;

    }

    //按照区间起点升序排序
    qsort(intervals,intervalsLen,sizeof(struct Interval),compare);

    //分配空间存储合并后的区间
    struct Interval* merged = (struct Interval*)malloc(intervalsLen * sizeof(struct Interval));
    if( !merged)
    {
        *returnSize = 0;
        return NULL;//内存分配失败
    }

    //初始化合并后的第一个区间
    merged[0].start = intervals[0].start;
    merged[0].end = intervals[0].end;

    int count = 1;//合并后的区间数量

    //遍历排序的区间
    for(int i = 1;i<intervalsLen;i++)
    {
        if(intervals[i].start <= merged[count-1].end)
        {
            merged[count-1].end = (intervals[i].end > merged[count-1].end) ? intervals[i].end : merged[count-1].end;
        }
        else//无重叠 
        {
            merged[count].start = intervals[i].start;
            merged[count].end = intervals[i].end;
            count++;
        } 
    }

    *returnSize = count;
    return merged;

}

大致思路：

先写一个比较函数，然后利用qsort函数对结构体数组进行排序。然后合并区间，如果当前区间与合并后的最后一个区间有重叠（即当前区间的起点小于等于合并后区间的终点），则更新合并后区间的终点。

如果当前区间与合并后的最后一个区间无重叠，则将当前区间直接添加到合并后的区间数组中。