题解 | #合并区间#

C语言

struct Interval* merge(struct Interval* intervals, int intervalsLen, int* returnSize ) {

    // write code here

    int tmpStart, tmpEnd;                   //当前开头，当前结尾

    int tmpMinStart, tmpMinEnd, tmp;        //未使用的当前最小起始区间的开头结尾

    struct Interval *retInterval = (struct Interval*)malloc(sizeof(struct Interval)*intervalsLen);    

    // int useFlag[5] = {1,1,1,1,1};  //本地测试代码

    int *useFlag = (int*)malloc(sizeof(int)*intervalsLen);    //未使用为1，已使用为0

    for(int i=0; i<intervalsLen; i++){

        *(useFlag+i) = 1;

    }

    *returnSize = 0;                        //初始化返回结构体的长度

    for(int i=0; i < intervalsLen; i++){    

        if(useFlag[i] == 0)                 //如果当前区间已使用，则跳过

            continue;

        tmpStart = intervals[i].start, tmpEnd = intervals[i].end;   //获得当前区间的起始和结尾

        tmpMinStart = -1, tmpMinEnd = -1;   //清空，初始化表示没找到最小起始区间

        useFlag[i] = 0;                     //标志当前区间已使用

        for(int j=i+1; j <= intervalsLen; j++){ //从当前区间下一个开始，循环

            if(j == intervalsLen){              //判断是否到最后一个区间

                if(tmpMinStart <= tmpEnd && tmpMinEnd >= tmpStart){   //intervals中还有未合并区间，则继续从当前区间的下一个进行循环

                    tmpMinStart = -1, tmpMinEnd = -1;

                    j = i;    //重新开始循环,相当于j=i+1

                    continue;

                }

                break;  

            }

            if(useFlag[j] == 0)             //如果当前区间已使用，则跳过

                continue;

            if(tmpStart <= intervals[j].end && tmpEnd >= intervals[j].start){    //当前区间与比较区间有重合

                useFlag[j] = 0;     //标志比较区间已使用

                tmpStart = tmpStart < intervals[j].start ? tmpStart : intervals[j].start ;//更新合并后区间的起始、结尾

                tmpEnd = tmpEnd > intervals[j].end ? tmpEnd : intervals[j].end;  

            }else{      //当前区间与比较区间没重合

                if(tmpMinStart == -1 || tmpMinStart > intervals[j].start){  //判断：1、未初始化，则赋初值 2、找到更小的起始区间

                    tmpMinStart = intervals[j].start;       //将未使用的区间且起始区间更小的比较区间记录

                    tmpMinEnd = intervals[j].end;

                }

            }

        }

        retInterval[*returnSize].start = tmpStart;      //将合并后的区间开头赋值

        retInterval[*returnSize].end = tmpEnd;          //将合并后的区间结尾赋值

        (*returnSize)++;                                //返回区间数量+1

    }

    for(int i=0; i<*returnSize; i++){                   //冒泡排序

        for(int j=i; j<*returnSize; j++){

            if(retInterval[i].start > retInterval[j].start){

                tmp = retInterval[i].start;

                retInterval[i].start = retInterval[j].start;

                retInterval[j].start = tmp;

                tmp = retInterval[i].end;

                retInterval[i].end = retInterval[j].end;

                retInterval[j].end = tmp;

            }

        }

    }

    return retInterval;

}