编辑代码

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

struct Section {
    int start;
    int end;
};

void printNonIntersectSections(struct Section *nonIntersectSections, int size) {
    for (int i = 0; i < size; ++i) {
        printf("[%d,%d] ", nonIntersectSections[i].start, nonIntersectSections[i].end);
    }

    printf("\n");
}

int compareSectionLength(const void *a, const void *b) {
    return (((struct Section *)a)->end - ((struct Section *)a)->start) -
           (((struct Section *)b)->end - ((struct Section *)b)->start);
}

int compareSectionStart(const void *a, const void *b) {
    return ((struct Section *)a)->start - ((struct Section *)b)->start;
}

void findNonIntersectSections(struct Section *sections, int size, struct Section *nonIntersectSections, int *nonIntersectSize) {
    //按照从小到大顺序对区间起始点进行排序
    qsort(sections, size, sizeof(struct Section), compareSectionStart);

    struct Section *selected = sections;

    while (selected < sections + size) {
        // 每次找出End最小的，因为它对期望值贡献最大
        int sectionEnd = selected->end;
        struct Section *minEnd = sections + size;

        for (struct Section *i = selected; i < sections + size; ++i) {
            printf("start: %d end: %d\n", i->start, i->end);
            printf("%d\n", sectionEnd);
            printf("%d\n", *nonIntersectSize);

            if (*nonIntersectSize > 0) {
                if ((nonIntersectSections + (*nonIntersectSize) - 1)->end <= i->start && sectionEnd >= i->end) {
                    printf("start: %d end: %d\n", (nonIntersectSections + (*nonIntersectSize) - 1)->start, (nonIntersectSections + (*nonIntersectSize) - 1)->end);
                    minEnd = i;
                    sectionEnd = i->end;
                }
            } else {
                if (sectionEnd >= i->end) {
                    minEnd = i;
                    sectionEnd = i->end;
                }
            }
        }

        if (minEnd != sections + size) {
            selected = minEnd;
            nonIntersectSections[*nonIntersectSize] = *selected;
            (*nonIntersectSize)++;
        }
        ++selected;
    }
}

int main() {
    struct Section sections[] = {
        {6, 8},
        {2, 4},
        {5, 9},
    };

    int size = sizeof(sections) / sizeof(sections[0]);

    struct Section nonIntersectSections[size];
    int nonIntersectSize = 0;

    findNonIntersectSections(sections, size, nonIntersectSections, &nonIntersectSize);

    printNonIntersectSections(nonIntersectSections, nonIntersectSize);

    return 0;
}