编辑代码

#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;
}
// 计算最多能选出多少个不相交的区间
int maxNonOverlappingIntervals(struct Interval intervals[], int n) {
    if (n <= 0) {
        return 0;
    }
    // 将区间按照结束端点从小到大排序
    qsort(intervals, n, sizeof(struct Interval), compare);
    int count = 1; // 至少有一个区间是不相交的
    int end = intervals[0].end;
    for (int i = 1; i < n; i++) {
        // 如果下一个区间的起始端点大于当前选定区间的结束端点，则选择该区间
        if (intervals[i].start > end) {
            count++;
            end = intervals[i].end;
        }
    }
    return count;
}
int main() {
    // 示例输入
    struct Interval intervals[] = {{1, 2}, {2, 4}, {3, 5}, {5, 7}, {8, 9}};
    int n = sizeof(intervals) / sizeof(intervals[0]);
    // 计算最多能选出多少个不相交的区间
    int result = maxNonOverlappingIntervals(intervals, n);
    // 输出结果
    printf("最多能选出%d个不相交的区间\n", result);
    return 0;
}