给出一组区间，请合并所有重叠的区间。
请保证合并后的区间按区间起点升序排列。
//"区间"定义
class Interval {
int start; //起点
int end; //终点
}
数据范围：区间组数 
，区间内 的值都满足 
要求：空间复杂度 )
，时间复杂度 )
进阶：空间复杂度 )
，时间复杂度
[编程题]合并区间
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)
#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
回复(0)
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)
/**
* 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;
}
* 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)
/**
* 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)
#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)
// 问题 运行超时。。。。
/**
* 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)
/**
* struct Interval {
* int start;
* int end;
* };
*/
* 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;
}
*
* @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)
问题信息
难度：
12条回答
1456收藏
30423浏览
通过挑战的用户
查看代码-
2023-03-10 13:59:15 -
2023-03-05 20:02:11 -
2023-03-04 16:26:47
-
2023-02-26 10:59:27
-
2023-02-24 20:59:27
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
