编辑代码

#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) {
    // 按照右端点排序
    qsort(intervals, n, sizeof(Interval), compareIntervals);

    // 初始化结果数组
    Interval result[n];
    int resultSize = 0;

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

    // 选择不冲突的区间
    for (int i = 0; i < n; ++i) {
        if (intervals[i].start > targetInterval.end) {
            result[resultSize++] = intervals[i];
            targetInterval = intervals[i];
        }
    }

    // 打印结果
    printf("Selected Intervals:\n");
    for (int i = 0; i < resultSize; ++i) {
        printf("[%d, %d] ", result[i].start, result[i].end);
    }
}

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

    // 调用区间覆盖算法
    intervalCover(intervals, n);

    return 0;
}