编辑代码

#include <stdio.h>

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

// 用于交换两个区间的函数
void swap(struct Interval* a, struct Interval* b) {
    struct Interval t = *a;
    *a = *b;
    *b = t;
}

int partition(struct Interval arr[], int low, int high) {
    int pivot = arr[high].end;
    int i = (low - 1);

    for (int j = low; j <= high - 1; j++) {
        if (arr[j].end < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quickSort(struct Interval arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

void intervalCover(struct Interval arr[], int n) {
    // 对区间按照结束位置进行快速排序
    quickSort(arr, 0, n - 1);

    int i = 0;
    while (i < n) {
        // 输出选择的区间
        printf("[%d, %d] ", arr[i].start, arr[i].end);
        
        // 找到下一个不重叠的区间
        int j = i + 1;
        while (j < n && arr[j].start < arr[i].end) {
            j++;
        }
        i = j;
    }
}

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

    printf("选定的间隔: \n");
    intervalCover(arr, n);

    return 0;
}