带期限的任务排序问题，fjs算法 出现的问题

Question

要求是 给定一系列任务，每个任务有截止时间点和效益 要找到效益最大的任务序列
做法是将任务按效益由大至小排序，然后依次选择，将任务放在截止时间点上，下一次如果有截止时间点相同的任务就放在其前一个时间点上，直至时间为0时说明没有时间点可放，那么要舍弃该任务，再判断下一个任务

实现思路是使用并查集，首先将每个时间点的根节点设为自己，遇到一个任务时就先判断其根节点是否为0，若不为0，将其截止时间点对应根节点赋给该任务，然后将其与前一个时间点所在集合合并，然后将该任务序号加入答案序列

输入
5
10 2
15 2
10 1
5 3
1 3
正确输出应该是1 2 4
程序输出 1 2 3 4，这是为什么?怎么修改代码?

Answer 1

|
已为你修改代码，望采纳。

|

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

#define N 1007

struct zy {
    int d, p, index;
};

struct zy zys[N];
int fa[N], sz[N];

// 比较函数，按照效益降序排序
int compare(const void *a, const void *b) {
    struct zy *za = (struct zy *)a;
    struct zy *zb = (struct zy *)b;
    return (zb->p - za->p);
}

// 查找根节点
int find(int i) {
    if (fa[i] == i) return i;
    else {
        fa[i] = find(fa[i]);
        return fa[i];
    }
}

// 合并节点
void merge(int x, int y) {
    x = find(x), y = find(y);
    sz[x] += sz[y];
    fa[y] = x;
}

int main() {
    int n;
    scanf("%d", &n);

    for (int i = 1; i <= n; ++i) {
        scanf("%d %d", &zys[i].p, &zys[i].d);
        zys[i].index = i;
    }

    // 按照效益降序排序
    qsort(zys + 1, n, sizeof(struct zy), compare);

    // 初始化并查集
    for (int i = 1; i <= n; ++i) {
        fa[i] = i;
        sz[i] = 1;
    }

    // 选择任务
    int ans[N], count = 0;
    for (int i = 1; i <= n; ++i) {
        if (find(zys[i].d) != 0) {
            ans[count++] = zys[i].index;
            merge(find(zys[i].d) - 1, find(zys[i].d));
        }
    }

    // 对结果排序
    qsort(ans, count, sizeof(int), compare);

    // 输出结果
    for (int i = 0; i < count; ++i) {
        printf("%d", ans[i]);
        if (i < count - 1) printf(" ");
    }

    return 0;
}