【输入样例】 10 1 8 2 7 3 4 4 2 5 5 6 1 7 9 8 3 9 10 10 6 【输出样例】 最大不相交子集:{(3,4),(5,5),(7,9),(9,10)}。C语言实现
时间: 2024-01-02 10:04:35 浏览: 36
同样的算法,使用 C 语言实现如下:
```c
#include <stdio.h>
#include <stdlib.h>
struct Interval {
int start;
int end;
};
int cmp(const void* a, const void* b) {
return ((struct Interval*)a)->end - ((struct Interval*)b)->end;
}
struct Interval* maxNonOverlapSet(struct Interval* intervals, int intervalsSize, int* returnSize) {
struct Interval* res = (struct Interval*)malloc(sizeof(struct Interval) * intervalsSize);
*returnSize = 0;
if (intervalsSize == 0) {
return res;
}
qsort(intervals, intervalsSize, sizeof(struct Interval), cmp);
res[(*returnSize)++] = intervals[0];
for (int i = 1; i < intervalsSize; i++) {
if (intervals[i].start >= res[*returnSize - 1].end) {
res[(*returnSize)++] = intervals[i];
}
}
return res;
}
int main() {
int n;
scanf("%d", &n);
struct Interval* intervals = (struct Interval*)malloc(sizeof(struct Interval) * n);
for (int i = 0; i < n; i++) {
int start, end;
scanf("%d %d", &start, &end);
intervals[i].start = start;
intervals[i].end = end;
}
int resSize;
struct Interval* res = maxNonOverlapSet(intervals, n, &resSize);
printf("最大不相交子集:{");
for (int i = 0; i < resSize; i++) {
printf("(%d,%d)", res[i].start, res[i].end);
if (i != resSize - 1) {
printf(",");
}
}
printf("}\n");
free(intervals);
free(res);
return 0;
}
```
输入样例:
```
10
1 8
2 7
3 4
4 2
5 5
6 1
7 9
8 3
9 10
10 6
```
输出样例:
```
最大不相交子集:{(3,4),(5,5),(7,9),(9,10)}
```