编辑代码

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

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

// 比较函数，用于qsort排序
int compareIntervals(const void *a, const void *b) {
    return ((struct Interval*)a)->end - ((struct Interval*)b)->end;
}

// 区间覆盖算法
void intervalCovering(struct Interval intervals[], int n) {
    // 按结束点升序排序
    qsort(intervals, n, sizeof(struct Interval), compareIntervals);

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

    // 遍历区间
    int i = 0;
    while (i < n) {
        // 选择当前区间
        result[resultCount] = intervals[i];
        resultCount++;

        // 跳过所有与当前区间相交的区间
        while (i < n - 1 && intervals[i + 1].start <= result[resultCount - 1].end) {
            i++;
        }
        i++;
    }

    // 输出结果
    printf("Minimum number of intervals needed: %d\n", resultCount);
    printf("Selected intervals: ");
    for (int j = 0; j < resultCount; j++) {
        printf("[%d, %d] ", result[j].start, result[j].end);
    }
    printf("\n");
}

int main() {
    // 示例输入
    struct Interval intervals[] = {{1, 3}, {2, 4}, {3, 5}, {5, 6}};
    int n = sizeof(intervals) / sizeof(intervals[0]);

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

    return 0;
}