首页 > 试题广场 >

合并区间

[编程题]合并区间
  • 热度指数：189104 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给出一组区间，请合并所有重叠的区间。
请保证合并后的区间按区间起点升序排列。 
//"区间"定义
class Interval {
   int start; //起点
   int end;   //终点
}

数据范围：区间组数 ，区间内 的值都满足
要求：空间复杂度 ，时间复杂度
进阶：空间复杂度 ，时间复杂度
示例1

输入

[[10,30],[20,60],[80,100],[150,180]]

输出

[[10,60],[80,100],[150,180]]
示例2

输入

[[0,10],[10,20]]

输出

[[0,20]]
算法知识视频讲解
添加回答
C
牛客562978599号头像 牛客562978599号
/**
 * struct Interval {
 *  int start;
 *  int end;
 * };
 */

//比较函数
int compare_func(const void*a,const void*b)
{
    struct Interval* start1 = (struct Interval*)a;
    struct Interval* start2 = (struct Interval*)b;
    return start1->start - start2->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
    struct Interval *result = (struct Interval*)malloc(intervalsLen*sizeof(struct Interval));
    int k =  0;
    int step = 1;
    int mem = 1;
    int flag = 0;

    //排序区间
    qsort(intervals,intervalsLen,sizeof(struct Interval),compare_func);

    for(int i =  0 ;i < intervalsLen;i += step)
    {
        if(i == intervalsLen - 1 && flag != 1)//最后一个未被合并时直接加入
        {
            result[k].start = intervals[intervalsLen - 1].start;
            result[k].end = intervals[intervalsLen - 1].end;
            k ++;
        }
        for(int j  = i+1; j < intervalsLen;j++)
        {
            if(intervals[i].end < intervals[j].start)//不满足条件，切换主体，并填充result数组
            {
                //将当前区间填入结构体数组
                result[k].start = intervals[i].start;
                result[k].end = intervals[i].end;
                k++;
                //对辅助步数进行设置，并重置计数
                step = mem;
                mem = 1;
                break;
            }
            else if(intervals[i].end >= intervals[j].start)//若满足合并区间的条件，则合并区间并计数
            {
                if(intervals[i].end <= intervals[j].end)
                {
                    intervals[i].end = intervals[j].end;

                }
                    mem++;
                if(j == intervalsLen-1)//最后一个被合并，则其不加入，并置标志位
                {
                    result[k].start = intervals[i].start;
                    result[k].end = intervals[i].end;
                    k ++;
                    flag = 1;
                    step = mem;
                }
            }
        }
    }
   
    *returnSize = k;
    return result;
}
发表于 2025-11-06 17:25:56 回复(0)
C
Daniel_shark头像 Daniel_shark
int cmp(const void* a, const void* b) {
    struct Interval* aa = (struct Interval*)a;
    struct Interval* bb = (struct Interval*)b;
    if (aa->start != bb->start) {
        return aa->start - bb->start;
    }
    return aa->end - bb->end;
}
struct Interval* merge(struct Interval* intervals, int intervalsLen,
                       int* returnSize ) {
    int index = 0;
    qsort(intervals, intervalsLen, sizeof(struct Interval), cmp);
    struct Interval* res = (struct Interval*)calloc(intervalsLen,
                           sizeof(struct Interval));
    if (intervalsLen == 0) {
        *returnSize = 0;
        return res;
    }
    res[index].start = intervals[0].start;
    res[index].end = intervals[0].end;

    for (int i = 1; i < intervalsLen; i++) {
        if (intervals[i].start <= res[index].end) {
            res[index].start = fmin(res[index].start, intervals[i].start);
            res[index].end = fmax(intervals[i].end, res[index].end);
        } else {
            index++;
            res[index].start = intervals[i].start;
            res[index].end = intervals[i].end;
        }
    }
    *returnSize = ++index;
    return res;
}
发表于 2025-05-29 10:05:53 回复(0)
C
湫湫宁头像 湫湫宁 
#define len 200000
#include <stdlib.h>
int com(const void* a, const void* b)
{
    return ((struct Interval *)a)->start - ((struct Interval *)b)->start;
}
struct Interval* merge(struct Interval* intervals, int intervalsLen, int* returnSize ) {
    // write code here
    int i, j = 0;
    // *returnSize = intervalsLen;
    struct Interval result[len];
    if(intervalsLen == 0)
    {
        return NULL;
    }

    qsort(intervals, intervalsLen, sizeof(struct Interval), com);
    result[0].start = intervals[0].start;
    result[0].end = intervals[0].end;
    for(i = 1; i < intervalsLen; i++)
    {
        if(result[j].end > intervals[i].end)
        {
            continue;
        }
        if(result[j].end >= intervals[i].start)
        {
            result[j].end = intervals[i].end;
        }
        else
        {
            j++;
            result[j].start = intervals[i].start;
            result[j].end = intervals[i].end;
        }
    }
    *returnSize = j + 1;
    return result;
}

发表于 2024-10-01 15:18:25 回复(1)
C
一个优雅的程序猿头像 一个优雅的程序猿 
void ChargeInterval(struct Interval* s, struct Interval* t)
{
    struct Interval buffer;
    memcpy((unsigned char*)&buffer, (unsigned char*)s, sizeof(struct Interval));
    memcpy((unsigned char*)s, (unsigned char*)t, sizeof(struct Interval));
    memcpy((unsigned char*)t, (unsigned char*)&buffer, sizeof(struct Interval));
}

struct Interval* merge(struct Interval* intervals, int intervalsLen, int* returnSize ) {
    // write code here
    struct Interval* returnIntervals;
    returnIntervals = (struct Interval*)malloc(intervalsLen * sizeof(struct Interval));
    memset((unsigned char*)returnIntervals, 0, intervalsLen * sizeof(struct Interval));
    if (!intervalsLen) {
        *returnSize = 0;
        return returnIntervals;
    }
    memcpy((unsigned char*)returnIntervals, (unsigned char*)intervals, intervalsLen * sizeof(struct Interval));
    *returnSize = intervalsLen;
    {
        long long i, j;
        for (i = 0; i < intervalsLen; i++) {
            if(returnIntervals[i].start<0 && returnIntervals[i].end<0)
                continue;
            for (j = 0; j < intervalsLen; j++) {
                if(i==j)
                    continue;
                if(returnIntervals[j].start<0 && returnIntervals[j].end<0)
                    continue;
                if(!(returnIntervals[i].start>returnIntervals[j].end || returnIntervals[i].end<returnIntervals[j].start)) {
                    struct Interval buffer;
                    memcpy((unsigned char*)&buffer, (unsigned char*)&returnIntervals[i], sizeof(struct Interval));
                    returnIntervals[i].start = (buffer.start>returnIntervals[j].start)?returnIntervals[j].start:buffer.start;
                    returnIntervals[i].end = (buffer.end<returnIntervals[j].end)?returnIntervals[j].end:buffer.end;
                    returnIntervals[j].start = -1;
                    returnIntervals[j].end = -1;
                }
            }
        }
        {
            struct Interval* buffer;
            buffer = (struct Interval*)malloc(intervalsLen * sizeof(struct Interval));
            memcpy((unsigned char*)buffer, (unsigned char*)returnIntervals, intervalsLen * sizeof(struct Interval));
            for (i=0,j=0; j<intervalsLen; j++) {
                if (!(returnIntervals[j].start<0 && returnIntervals[j].end<0)) {
                    memcpy((unsigned char*)&returnIntervals[i], (unsigned char*)&buffer[j], sizeof(struct Interval));
                    i++;
                }
            }
            (*returnSize) = i;
        }
        
        for (i = 0; i < (*returnSize); i++)
            for (j = i; j < (*returnSize); j++) {
                if (returnIntervals[j].start < returnIntervals[i].start) 
                    ChargeInterval(&(returnIntervals[i]),&(returnIntervals[j]));
            }
    }

    return returnIntervals;
}

编辑于 2024-03-13 15:26:56 回复(0)
C
牛客486301874号头像 牛客486301874号
/**
 * struct Interval {
 *    int start;
 *    int end;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param intervals Interval类一维数组 
 * @param intervalsLen int intervals数组长度
 * @return Interval类一维数组
 * @return int* returnSize 返回数组行数
 */
 #include <stdlib.h>
int cmp(const void* a,const void* b)//结构体排序，以start的值升序排列
 {
     return (*(struct Interval*)a).start-(*(struct Interval*)b).start;
 }
 int ismerge(struct Interval a,struct Interval b)//检查两区间可否合并
 {
    if(a.end>=b.start)
    return 1;
    else
     return 0;
 }
struct Interval* merge(struct Interval* intervals, int intervalsLen, int* returnSize ) {
    int i=0;
    int j;
    if(intervalsLen==0)
    {
        return intervals;
    }
    for(int k=0;k<intervalsLen;k++)
    scanf("[%d,%d]",&intervals[i].start,&intervals[i].end);
    qsort(intervals,intervalsLen,sizeof(struct Interval),cmp);
    for( i=0,j=1;j<intervalsLen;j++)
    {
    if(ismerge(intervals[i],intervals[j]))//如果两区间可合并
    {
        //新区间的start是两者的较小值，end是两者的较大值
        if(intervals[i].start>intervals[j].start)
        intervals[i].start=intervals[j].start;
        if(intervals[i].end<intervals[j].end)
        intervals[i].end=intervals[j].end;
    }
   else //两区间不能合并，则让j区间覆盖i+1区间
      {
        ++i;
        intervals[i].start=intervals[j].start;
        intervals[i].end=intervals[j].end;
      } 
}
   *returnSize=i+1;
   return intervals;
    
}
编辑于 2024-01-07 18:18:26 回复(0)
C
牛客320056090号头像 牛客320056090号 
/**
 * struct Interval {
 *    int start;
 *    int end;
 * };
 */

/**
 * 
 * @param intervals Interval类一维数组 
 * @param intervalsLen int intervals数组长度
 * @return Interval类一维数组
 * @return int* returnSize 返回数组行数
 */
#include <stdlib.h>
#include <string.h>

int compare(const void* _a, const void* _b)
{
    struct Interval* a = (struct Interval *)_a;
    struct Interval* b = (struct Interval *)_b; 

    if(a->start != b->start)
    {
        return a->start - b->start;
    }
    else
    {
        return a->end - b->end;
    }
}

struct Interval* merge(struct Interval* intervals, int intervalsLen, int* returnSize ) {
    // write code here
    struct Interval tmp[intervalsLen];
    int index = 0;
    memset(tmp, -1, intervalsLen*sizeof(intervals[0]));
  
      //区间排序
    qsort(intervals, intervalsLen, sizeof(intervals[0]), compare);
  
    for(int i = 0; i < intervalsLen; i++)
    {
          //未操作的结构体赋初值
        if(tmp[index].start == -1)
        {
            tmp[index].start = intervals[i].start;
            tmp[index].end = intervals[i].end;
        }
      
        //末位防止溢出
        if(i == intervalsLen-1)
        {

            tmp[index].end = intervals[i].end > tmp[index].end ? intervals[i].end : tmp[index].end;
            index++;
            break;
        }
      
        //当前区间尾大于下个区间尾则直接进入下一次循环
        if(tmp[index].end >= intervals[i+1].end)
        {
            continue;
        }
      
        //当前区间尾大于下个区间头合并区间，否则结束当前区间，并索引后移一位
        if(intervals[i].end >= intervals[i+1].start)
        {
            tmp[index].end = intervals[i+1].end;
        }
        else
        {
            tmp[index].end = intervals[i].end;
            index++;
        }
    }

    *returnSize = index;
    memcpy(intervals, tmp, index*sizeof(intervals[0]));
    return intervals;
}
发表于 2023-03-28 17:17:47 回复(0)
C
我是小安哥头像 我是小安哥
#include <stdlib.h>
int compare(const void *pta,const void *ptb)
{
    struct Interval* ptaa = (struct Interval*)pta;
    struct Interval* ptbb = (struct Interval*)ptb;
    return ptaa->start - ptbb->start;

}

struct Interval* merge(struct Interval* intervals, int intervalsLen, int* returnSize ) {
    *returnSize = intervalsLen;
    int counter = 0;
    if(intervalsLen == 0 || intervalsLen == 1)
    {
        return intervals;
    }
    qsort(intervals, intervalsLen, sizeof(intervals[0]), compare);

    struct Interval* ReturnVals = (struct Interval*) malloc(sizeof(struct Interval) *intervalsLen);
    ReturnVals[0].start = intervals[0].start;
    ReturnVals[0].end = intervals[0].end;

    for(int i = 1; i < intervalsLen; i++)
    {
        if(ReturnVals[counter].end >= intervals[i].end)//包含
        {
           continue;
        }
        if(ReturnVals[counter].end < intervals[i].start)//无公共部分
        {
            counter++;
            ReturnVals[counter].start = intervals[i].start;
            ReturnVals[counter].end = intervals[i].end;
        }
        else//相交
        {
            ReturnVals[counter].end = intervals[i].end;
        }
    }
    *returnSize = counter+1;
    return ReturnVals;
}
发表于 2023-03-18 11:39:24 回复(0)
C
wkyang头像 wkyang 
// 问题  运行超时。。。。

/**
 * struct Interval {
 *	int start;
 *	int end;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

/**
 * 
 * @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
    
    
    struct Interval merg[200000];
    int k1 = 0;
    int k = 0;
    int vis[200000];
    memset(vis,0, sizeof(vis));
    
    // 先排序
    for(int i=0;i<intervalsLen;i++){
        for(int j=i+1;j<intervalsLen;j++){
            if(intervals[i].start>intervals[j].start){
                struct Interval tmp = intervals[i];
                intervals[i] = intervals[j];
                intervals[j] = tmp;
            }
        }
    }
    for(int i=0;i<intervalsLen;i++){
        if(vis[i]==1)
            continue;
        vis[i] = 1;
        for(int j = i+1;j<intervalsLen;j++){
            if(vis[j]==1)
                continue;
            if(intervals[i].end>=intervals[j].end){
                if(intervals[j].start>=intervals[i].start){ // j区间包含在i区间内 必须先判断     
                    vis[j]=1;
                }
                else if(intervals[j].end>=intervals[i].start){
                    intervals[i].start = intervals[j].start;
                    vis[j]=1;
                }
            }
            else if(intervals[j].end>=intervals[i].end){
                if(intervals[i].start>=intervals[j].start){ // i区间包含在j区间内
                    intervals[i] = intervals[j];
                    vis[j]=1;
                }
                else if(intervals[i].end>=intervals[j].start){
                    intervals[i].end = intervals[j].end;
                    vis[j]=1;
                }
            }
        }
        merg[k++] = intervals[i];
    }
    
    *returnSize = k;
    return merg;
}

发表于 2022-04-04 11:32:29 回复(0)
C
海饼干666头像 海饼干666
/**
 * struct Interval {
 * int start;
 * int end;
 * };
 */
/**
 *
 * @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 == 0)
    {
        *returnSize = 0;
        return NULL;
    }
    else if(intervalsLen == 1)
    {
        *returnSize = 1;
        return intervals;
    }
   
    for(int i = 0; i < intervalsLen-1; i++)
    {
        for(int j = i+1; j < intervalsLen; j++)
        {
            if(intervals[i].start > intervals[j].start)
            {
                struct Interval Tmp;
                Tmp = intervals[i];
                intervals[i] = intervals[j];
                intervals[j] = Tmp;
            }
        }
    }
   
    struct Interval *Retintervals = (struct Interval *)malloc(sizeof(struct Interval)*intervalsLen);
    memset(Retintervals, 0, intervalsLen*sizeof(struct Interval));
   
    *returnSize = 0;
    Retintervals[*returnSize] = intervals[0];
   
    for(int i = 1; i < intervalsLen; i++)
    {
        if(intervals[i].start <= Retintervals[*returnSize].end)
        {
            if(intervals[i].end > Retintervals[*returnSize].end)
            {
                Retintervals[*returnSize].end = intervals[i].end;
            }
            else if(intervals[i].end <= Retintervals[*returnSize].end && intervals[i].start >= Retintervals[*returnSize].start)
            {
                continue;
            }
        }
        else
        {
            *returnSize = *returnSize + 1;
            Retintervals[*returnSize] = intervals[i];
        }
    }
   
    *returnSize = *returnSize + 1;
    return Retintervals;
}
发表于 2021-08-28 16:19:14 回复(0)
提交观点

问题信息

数组 排序
难度：
13条回答 32342浏览

热门推荐

通过挑战的用户

查看代码

相关试题

合并区间

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号