活动选择问题 (Activity-selection problem)

问题

将定有一个 n 个活动的集合 S = {a[1], a[2], ..., a[n]}, 这些活动使用同一个资源， 而这个资源在某个时刻只能供一个活动使用。 每个活动都有一个开始时间 s[i] 和一个结束时间 f[i], 其中 0 <= s[i] < f[i] < $$\infty$$. 若 s[i] >= f[j] 或 s[j] >= f[i] 则 a[i] 和 z[j] 是兼容的
问题：选出一个最大兼容活动集，假定活动已按结束时间单调递增顺序排序：

f[1] <= f[2] <= f[3] <= ... <= f[n-1] <= f[n]

例如下面的活动集合：

那么 {a[1], a[4], a[8], a[11]} 是一个最大兼容活动子集，另一个是 {a[2], a[4], a[9], a[11]}

思路

直觉告诉我们，应该选择 S 中最早结束的活动，因为它剩下的资源可供它之后尽量多的活动来使用
当作出贪心选择之后，只剩下一个子问题需要我们求解：寻找在 a[1] 结束之后开始的活动

一下定理可被证明：
考虑任意非空子问题 S[k], 令 a[m] 是 S[k] 中结束时间最早的活动， 则 a[m] 在 S[k] 的某个最大兼容活动子集中

求解活动选择问题的算法不必像基于表格的动态规划算法那样自底向上进行计算。 相反，可以自顶向下进行计算，选择一个活动放入最优解，然后对剩下的子问题进行求解。 贪心算法通常都是这种自顶向下的设计：作出一个选择，然后求解剩下的那个子问题， 而不是自底向上地求解出很多子问题，然后再作出选择

代码

(define (activity-selector act)
  (define (iter act end)
    (cond [(empty? act)
           '()]
          [(> (caar act) end)
           (cons (car act)
                 (iter (cdr act) (cadar act)))]
          [else
           (iter (cdr act) end)]))
  (iter act -1))

(define act '((1 4) (3 5) (0 6) (5 7) (3 9) (5 9) (6 10)
                    (8 11) (8 12) (2 14) (12 16)))

(activity-selector act)