活动选择问题

活动选择问题是一个数学优化问题。我们的第一个例子是关于在几个挑战活动中安排资源的问题。我们发现贪心算法提供了一种设计良好且简单的方法，用于选择最大大小的一组手动兼容的活动。

假设 S = {1, 2....n} 是 n 个提议活动的集合。这些活动共享资源，这些资源一次只能被一个活动使用，例如，网球场，演讲厅等。每个活动“i”都有 开始时间 s_i 和 结束时间 f_i，其中 s_i ≤f_i。如果选择活动“i”，则发生在半开时间间隔 [s_i,f_i)。活动 i 和 j 是 兼容的，如果区间 (s_i, f_i) 和 [s_i, f_i) 不重叠（即，如果 s_i ≥f_i 或 s_i ≥f_i，则 i 和 j 兼容）。活动选择问题选择最大大小的相互一致的活动集合。

贪心算法选择器算法

GREEDY- ACTIVITY SELECTOR (s, f)
1. n ← length [s]
2. A ← {1}
3. j ← 1.
4. for i ← 2 to n
5. do if si ≥ fi
6. then A ← A ∪ {i}
7. j ← i
8. return A

示例： 给定 10 个活动以及它们的开始和结束时间，如下所示

S = (A1 A2 A3 A4 A5 A6 A7 A8 A9 A10)
Si = (1,2,3,4,7,8,9,9,11,12)
fi = (3,5,4,7,10,9,11,13,12,14)

计算一个日程安排，其中发生最多数量的活动。

解决方案： 使用贪心策略解决上述活动调度问题的示例如下所示

按结束时间的升序排列活动

现在，安排 A₁

接下来安排 A₃，因为 A₁ 和 A₃ 不互相干扰。

接下来 跳过 A₂，因为它会干扰。

接下来，安排 A₄，因为 A₁ A₃ 和 A₄ 不互相干扰，然后接下来，安排 A₆，因为 A₁ A₃ A₄ 和 A₆ 不互相干扰。

跳过 A₅，因为它会干扰。

接下来，安排 A₇，因为 A₁ A₃ A₄ A₆ 和 A₇ 不互相干扰。

接下来，安排 A₉，因为 A₁ A₃ A₄ A₆ A₇ 和 A₉ 不互相干扰。

跳过 A₈，因为它会干扰。

接下来，安排 A₁₀，因为 A₁ A₃ A₄ A₆ A₇ A₉ 和 A₁₀ 不互相干扰。

因此，最终的活动安排是