编辑代码

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

// 定义区间的结构体
struct Interval {
    int start;
    int end;
};

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

// 贪心算法解决区间覆盖问题
void intervalCover(struct Interval *intervals, int num_intervals) {
    // 按照右端点升序排序
    qsort(intervals, num_intervals, sizeof(struct Interval), compare);

    // 选择第一个区间
    struct Interval current_interval = intervals[0];
    printf("选取区间 [%d, %d]\n", current_interval.start, current_interval.end);

    // 遍历区间并选择
    for (int i = 1; i < num_intervals; i++) {
        if (intervals[i].start > current_interval.end) {
            // 区间不重叠，选择该区间
            current_interval = intervals[i];
            printf("选取区间 [%d, %d]\n", current_interval.start, current_interval.end);
        }
    }
}

int main() {
    // 示例数据
    struct Interval intervals[] = {
        {1, 3},
        {2, 4},
        {3, 6},
        {5, 7},
        {8, 10},
        {9, 12}
    };

    int num_intervals = sizeof(intervals) / sizeof(intervals[0]);

    printf("区间覆盖问题解决方案：\n");
    intervalCover(intervals, num_intervals);

    return 0;
}