编辑代码

#include <stdio.h>
#include <stdlib.h>

// 区间结构体
typedef struct {
    int start;
    int end;
} Interval;

// 按照右端点排序的比较函数
int compareIntervals(const void *a, const void *b) {
    return ((Interval*)a)->end - ((Interval*)b)->end;
}

// 区间覆盖的贪心算法
void intervalCover(Interval intervals[], int n, int* resultSize) {
    // 按照右端点排序
    qsort(intervals, n, sizeof(Interval), compareIntervals);

    // 目标区间的起始和结束点
    Interval targetInterval = {-1, -1};

    // 选择不冲突的区间并打印
    for (int i = 0; i < n; ++i) {
        if (intervals[i].start > targetInterval.end) {
            printf("[%d, %d] ", intervals[i].start, intervals[i].end);
            targetInterval = intervals[i];
            (*resultSize)++;
        }
    }
}

int main() {
    // 示例输入，包含一些区间
    Interval intervals[] = {{1, 9}, {3, 7}, {4, 8}, {5, 10}, {7, 55},{10,66}};
    int n = sizeof(intervals) / sizeof(intervals[0]);

    // 调用区间覆盖算法
    int resultSize = 0;
    printf("区间:\n");
    intervalCover(intervals, n, &resultSize);
    printf("\n结果大小: %d\n", resultSize);

    return 0;
}