使用完整的C语言实现:无重叠区间 Description 给定一个区间的集合 intervals ,其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量,使剩余区间互不重叠 。 Input 一个整数n表示集合中区间个数 接下来n行表示n个区间 Output 一个整数,表示需要移除区间的最小数量 Sample Input 1 4 1 2 2 3 3 4 1 3 Sample Output 1 1 Sample Input 2 2 1 2 2 3 Sample Output 2 0
时间: 2024-01-17 11:05:53 浏览: 31
好的,我会根据你的要求回答问题。关于你的问题,以下是使用完整的C语言实现无重叠区间的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义区间结构体
typedef struct Interval {
int start;
int end;
} Interval;
// 比较函数,用于排序
int cmp(const void *a, const void *b) {
Interval *ia = (Interval *)a;
Interval *ib = (Interval *)b;
return ia->end - ib->end;
}
int eraseOverlapIntervals(Interval *intervals, int intervalsSize){
if (intervalsSize <= 1) {
return 0;
}
// 按照区间结尾排序
qsort(intervals, intervalsSize, sizeof(Interval), cmp);
int count = 1; // 记录不重叠的区间数量
int end = intervals[0].end; // 记录当前不重叠区间的结尾
for (int i = 1; i < intervalsSize; i++) {
if (intervals[i].start >= end) { // 如果当前区间的开头大于等于上一个区间的结尾,说明不重叠
count++;
end = intervals[i].end;
}
}
return intervalsSize - count; // 总区间数减去不重叠区间数就是需要移除的最小数量
}
int main() {
int n;
scanf("%d", &n);
Interval *intervals = (Interval *)malloc(sizeof(Interval) * n);
for (int i = 0; i < n; i++) {
scanf("%d %d", &(intervals[i].start), &(intervals[i].end));
}
int result = eraseOverlapIntervals(intervals, n);
printf("%d\n", result);
free(intervals);
return 0;
}
```
使用贪心算法,将区间按照结尾从小到大排序,然后从第二个区间开始遍历,如果当前区间的开头大于等于上一个区间的结尾,说明不重叠,将计数器加1,并更新当前不重叠区间的结尾。最后,用总区间数减去不重叠区间数,就是需要移除的最小数量。