活动安排问题
- 简介
- 活动安排问题是需要共享公共资源的一系列活动的高效安排问题，以在限定的资源前提下尽可能多地安排活动。一般，算法题中给出开始结束时间的活动序列都可以使用这种贪心思路。
- 问题描述
- 有若干个活动，第i个活动的开始时间和结束时间是[Si,fi)，只有一间教室，活动之间不能交叉，即一个活动结束后另一个才能开始，求解最多能安排多少个活动？
- 问题分析
- 目的是提高教室的利用率，尽可能多地安排活动。
- 不妨考虑几种容易想到的贪心策略。
- 开始最早的活动优先
- 短活动优先
- 看一个反例,[0,5),[5,10),[3,7)这里面最后的[3,7)最短，但是一旦安排了这个另外两个就无法安排了，显然，不合理。
- 最少冲突的活动优先
- 优先安排少的活动怎么样呢？
- 看个例子
- [0,2),[2,4),[4,6),[6,8)
- [1,3),[1,3),[1,3),[3,5),[5,7),[5,7),[5,7)
- 第一行应该可以一起安排出来，但是按照冲突最少策略，最多安排三个活动。
- 结束时间越早的活动优先
- 这是看起来最不合理的，但是，可以证明一下。
- 假设最优解OPT中安排了m个活动，我们把这些活动按照结束时间由小到大排序，显然不冲突。假设排好顺序后，这些活动是a(1),a(2)…a(m)。
- 按照贪心策略，选出的活动自然是按照结束时间排好序的，并且也都是不冲突的，这些活动为b(1),b(2)…b(n)。
- 关键问题是，假设a(1)=b(1),a(2)=b(2)…a(k)=b(k),但是a(k+1)!=b(k+1)，回答下面的问题
- b(k+1)会在a(k+2),a(k+3)…a(m)中吗？
- 不会，因为b(k+1)的结束时间最早（我们就是如此贪心选择的），即f(b(k+1))<=f(a(k+1))，而a(k+2),a(k+3),a(m)的开始结束时间都在f(a(k+1))之后，所以b(k+1)不在其中。
- b(k+1)和a(1),a(2),a(k)冲突吗？
- 不冲突，因为a(1),a(2),a(k)就是(1),b(2),b(k)。
- b(k+1)和a(k+2),a(k+3),a(m)冲突吗？
- 不冲突，因为f(b(k+1))<=f(a(k+1))，而a(k+2),a(k+3),a(m)的开始时间都在f(a(k+1))之后，更在f(b(k+1))之后了。
- 因此，可以把a(k+1)换成b(k+1)，从而最优解和贪心的解多了一个相同的，经过一个一个替换，可以把最优解完全替换成贪心策略得到的解，从而证明这个贪心策略的最优性。
- 代码
-
def bubble_sort(s, f):"""冒泡排序对结束时间排序，同时得到对应的开始时间的list:param s::param f::return:"""for i in range(len(f)):for j in range(0, len(f)-i-1):if f[j] > f[j+1]:f[j], f[j+1] = f[j+1], f[j]s[j], s[j+1] = s[j+1], s[j]return s, fdef greedy(s, f, n):a = [True for x in range(n)]j =0for i in range(1, n):if s[i] >= f[j]:a[i] = Truej = ielse:a[i] = Falsereturn aif __name__ == '__main__':s = [1, 2, 3, 5, 8]f = [3, 4, 5, 7, 9]s, f = bubble_sort(s, f)A = greedy(s, f, len(s))res = []for k in range(len(A)):if A[k]:res.append('({}, {})'.format(s[k], f[k]))print(''.join(res))
- 运行结果
- 补充说明
- 具体代码可以查看我的Github，欢迎Star或者Fork
- 参考书《你也能看得懂的Python算法书》
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！
