C语言 | Leetcode C语言题解之第436题寻找右区间

题目：

题解：

typedef struct {
    int start;
    int index;
} Node;

int cmp(const void *pa, const void *pb) {
    return ((Node *)pa)->start - ((Node *)pb)->start;
}

int* findRightInterval(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize){
    Node * startIntervals = (Node *)malloc(sizeof(Node) * intervalsSize);
    Node * endIntervals = (Node *)malloc(sizeof(Node) * intervalsSize);
    for (int i = 0; i < intervalsSize; i++) {
        startIntervals[i].start = intervals[i][0];
        startIntervals[i].index = i;
        endIntervals[i].start = intervals[i][1];
        endIntervals[i].index = i;
    }
    qsort(startIntervals, intervalsSize, sizeof(Node), cmp);
    qsort(endIntervals, intervalsSize, sizeof(Node), cmp);

    int * ans = (int *)malloc(sizeof(int) * intervalsSize);
    for (int i = 0, j = 0; i < intervalsSize; i++) {
        while (j < intervalsSize && endIntervals[i].start > startIntervals[j].start) {
            j++;
        }
        if (j < intervalsSize) {
            ans[endIntervals[i].index] = startIntervals[j].index;
        } else {
            ans[endIntervals[i].index] = -1;
        }
    }
    *returnSize = intervalsSize;
    free(startIntervals);
    free(endIntervals);
    return ans;
}