我寻找最小重叠作业集的算法正确吗？

Question

最近进行了一次测试，我的解决方案得到了 0 分，并有评论说算法不正确（不是证明，而是算法本身）。 他们给出的反例不正确，所以我想知道是正确的还是我的算法实际上是错误的。

问题来了：

给定一组 n 个作业 (a_1, a_2, ..., a_n)，每个作业都有设定的开始时间 (s_i) 和结束时间 (f_i)（很可能重叠），找到作业 A 的最小子集，例如对于每个作业 a_i，它要么包含在 A 中，要么 A 中存在另一个作业 a_j，这样 a_i 和 a_j 就会重叠。

举个例子：

给定作业 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_1<= s_2 <= ... <= s_n)

2. 令 C = a1、M = m = f_1 和 A 为空集。

3. 对于 i=1, 2, ..., n

   3.1) 如果 s_i > M:

      - A = A U {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. A = A U {c}

5. 返回A

任何帮助表示赞赏，

谢谢

Answer 1

它很难破译你的算法，但它似乎失败了

[1,3], [2,4], [3,5], [4,6], [5,7]

这个问题可以用贪心算法解决，如下：

1. 找到最早结束时间的间隔T。 请注意，所有在 T.end 之前开始的区间都会与 T 重叠。从问题定义来看，结果集中至少需要有一个与 T 重叠的区间；
2. 从与T（包括T）重叠的所有间隔中，选择结束时间最晚的一个X。 这是最佳的，因为与 X 重叠的间隔集合保证包括由结束时间较早的候选者重叠的任何间隔。
3. 将 X 复制到结果集中，然后删除 X 及其重叠的所有区间。删除的区间包括开始时间早于 X.end 的所有区间。

通过为步骤 (1) 的剩余间隔结束时间以及步骤 (2) 和 (3) 的剩余间隔开始时间单独制作升序列表，可以很容易地在 O(n log n) 时间内完成此操作。