编辑代码

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

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

// 比较函数，按照区间的右端点升序排序
int compare(const void* a, const void* b) {
    Interval* intervalA = (Interval*)a;
    Interval* intervalB = (Interval*)b;
    return intervalA->end - intervalB->end;
}

int intervalCover(Interval intervals[], int numIntervals, Interval target) {
    int count = 0;
    int targetEnd = target.end;
    int i;

    // 按照右端点升序排序
    qsort(intervals, numIntervals, sizeof(Interval), compare);

    // 贪心选择区间
    for (i = 0; i < numIntervals; i++) {
        if (intervals[i].start > targetEnd) {
            break;
        }
        if (intervals[i].end >= target.start) {
            count++;
            targetEnd = intervals[i].end;
        }
    }

    return count;
}

int main() {
    // 示例用法
    Interval intervals[] = {{1, 4}, {2, 5}, {7, 9}, {8, 11}};
    int numIntervals = sizeof(intervals) / sizeof(intervals[0]);
    Interval target = {2, 10};

    int minimumIntervals = intervalCover(intervals, numIntervals, target);
    printf("Minimum number of intervals needed: %d\n", minimumIntervals);

    return 0;
}