我的最小重叠作业覆盖集算法是否正确？请帮忙验证

我最近参加了一场测试，提交的解决方案得分为0，评语指出算法本身不正确（非证明类问题）。但我认为测试给出的反例有误，想请大家帮忙确认我的算法是否真的存在错误。

问题描述 #

给定n个作业集合$(a₁, a₂, ..., aₙ)$，每个作业包含起始时间$s_i$和结束时间$f_i$（作业间可能存在大量重叠），需要找到最小的作业子集A，满足：每个作业$a_i$要么属于A，要么存在A中的作业$a_j$与$a_i$重叠。

示例 #

• 作业集合：$a1(1, 3)$、$a2(2,4)$、$a3(3,5)$，最优结果集$A={a2}$
• 作业集合：$a1(1, 3)$、$a2(2,4)$、$a3(4,5)$，最优结果集$A={a1, a3}$或$A={a2, a3}$

我的算法步骤 #

1. 将所有作业按起始时间非降序排序（排序后满足$s₁≤s₂≤…≤sₙ$）
2. 初始化：$C=a1$，$M=m=f₁$，$A$为空集
3. 遍历每个作业$i=1,2,…,n$：
   3.1) 若$s_i > M$：
   - 将$C$加入集合$A$（$A = A ∪ {C}$）
   - 更新$C=a_i$，$m = M = f_i$
   3.2) 否则若$f_i > M$且$s_i < m$：
   - 更新$M=f_i$，$C=a_i$
   3.3) 更新$m = min(m, f_i)$
4. 遍历结束后，将最后一个$C$加入$A$（$A = A ∪ {C}$）
5. 返回集合$A$

恳请各位帮忙验证，谢谢！

内容的提问来源于stack exchange，提问作者itay