编辑代码

#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 selectNonOverlappingIntervals(struct Interval intervals[], int n) {
    // 按结束端点升序排序
    qsort(intervals, n, sizeof(struct Interval), compare);

    // 初始化结果和当前的结束端点
    int result = 1;
    int currentEnd = intervals[0].end;

    // 输出结果
    printf("区间:\n");
    printf("(%d, %d)\n", intervals[0].start, intervals[0].end);

    // 遍历区间，选择两两不相交的区间
    for (int i = 1; i < n; i++) {
        if (intervals[i].start > currentEnd) {
            result++;
            currentEnd = intervals[i].end;
            printf("(%d, %d)\n", intervals[i].start, intervals[i].end);
        }
    }

    // 输出最终结果
    printf("最大区间数: %d\n", result);
}

int main() {
    struct Interval intervals[] = {
        {6, 8},
        {2, 4},
        {3, 5},
        {1, 5},
        {5, 9},
        {8, 10}
    };
    int n = sizeof(intervals) / sizeof(intervals[0]);

    selectNonOverlappingIntervals(intervals, n);

    return 0;
}