435、452 活动选择问题、排课问题
|
例题：活动选择问题 点击此处返回总目录 习题1、435 无重叠区间 习题2、452 用最少数量的箭引爆气球
例题：活动选择问题 活动选择问题，电影节问题，排课问题等，虽然场景不一样，但意思一样，是同一个问题。
【题目】 一天里面有很多活动。每个活动有开始时间和结束时间，区间重叠的活动不能同时参与（端点重合可以）。问李静最多可以参加多少个活动。
输入： 12 //一共有12部电影 1 3 //第1部电影的开始和结束时间 3 4 0 7 3 8 15 19 15 20 10 15 8 18 6 12 5 10 4 14 2 9
输出： 5
【分析】 贪心算法的计算过程是一个多步的判断过程。每一步的判断都是根据某种“短视”的策略（就是只看眼前）进行活动选择，选择的时候注意满足相容性条件。 本题中，我们考虑有哪些可能的策略。 策略一：开始时间最早的优先。 首先按照开始时间排序，然后从前往后陆续挑活动，挑的时候注意后面的活动一定要和前面的活动相容。 策略二：占用时间少的优先。 首先按照占用时间排序，然后挑选。 策略三：哪个活动结束的早， 哪个活动优先。 首先按照活动结束时间排序，然后挑选。
上面三种策略，是否可行呢？ 第一种策略并不能得到最优解。比如： 上图中，活动1开始时间最早。但是最优解是选2和3。
第二种策略也不能得到最优解。比如： 上图中，活动3时间最少。但最优解是1和2。
我们采用策略三来做。（后面将证明）
【代码】
【结果】
时间复杂度：首先按照结束时间排序O(nlogn)，然后再一轮选择O(n)。总的为nlogn+n。
【正确性证明】
替换法。 假设用贪心方法挑选的电影序列为：a1,a2... 不用贪心法挑选的最长的电影序列为：b1,b2... 可以证明，对于任意的i，bi均可以替换为ai。这样b是最长的，那a也是最长的。
用数学归纳法证明。 用S(x)表示x的开始时间，E(x)表示x的结束时间，则： 1) b1可以替换为a1，且E(a1)<=E(b1)。因为我挑选的策略是选择结束时间最早的活动，所以a1的结束时间早于b1的结束时间，即E(a1)<=E(b1)。既然b1与后面的序列不冲突，那么a1也与后面的序列不冲突。所以a1可以替换b1。 2) ai可以替换bi且E(ai)<=E(bi) ======》 ai+1 可以替换bi+1，且E(ai+1)<=E(bi+1)。 证明：因为E(ai)<=S(bi)，又有E(bi)<=S(bi+1)，所以E(ai)<=S(bi+1)。即bi+1是ai的结束时间之后才开始的一个活动。 在我们的贪心策略中，ai+1的结束时间是ai的结束时间之后的活动中，结束时间最早的。 所以ai+1的结束时间一定小于bi+1的结束时间，即E(ai+1)<=E(bi+1)。 所以若ai可以替换bi且E(ai)<=E(bi),则ai+1就可以替换bi+1，且E(ai+1)<=E(bi+1)。 由数学归纳法，ai都可以替换bi，所以ai也是最长的电影序列。
---------------------------------------------------------------------------------------------------------------------- 习题1、435 无重叠区间 【题目】
【分析】 这就是活动安排问题。问最少移除多少个区间使得区间不重叠。就相当于最多保留多少个区间不重叠。
【代码】
【结果】
【分析】 结果，只有79%，不是太好。我看到6ms的算法也是这样写的。但是我没有跑出6ms的结果。 另外，3ms的做法是这样的： 结果： 而且，每次它都能跑出3ms的结果。 他的思想也是先结束的课程优先。只不过写法不一样。他是：首先按照课程开始时间排序，然后依次遍历后面的课程，如果发现有课程先结束，就把本课程删掉。。。 有兴趣的同学可以看看。 我认为他这种写法不怎么直观，不好理解。也看不出他为什么比我的跑的快。 我还是坚持我自己的方法。
---------------------------------------------------------------------------------------------------------------------- 习题2、452 用最少数量的箭引爆气球
【题目】
【分析】 这道题的难点在于读题。 理解了题意之后发现就是一个区间选择问题。每个气球有一个开始点和结束点。气球重合的地方可以一箭穿过去。 问至少射几箭，也就是问最多有多少个不重叠的区间。这是为什么呢？ 首先，不重叠的区间，肯定需要分别射箭穿过去。因此有多少不重叠的区间，就至少要放多少只箭。这个很好理解。 其次，对于剩下的区间，不需要额外的箭。这个不是很好想。我们这样想： 对于剩下的区间，肯定是跟不重叠区间有重合（否则它也就被选择为不重叠区间了）。我们在选择不重叠区间的时候，这两种选不上： （1）开始时间与前面已经选的区间有冲突。比如红色是已经选的不重叠区间，黑色的区间则不能选上。因为黑色区间的开始时间早于红色的结束时间。 （2）开始时间没有冲突，但是结束时间有更早的，也选不上。比如，下面这种，黑色虽然与第一个红色的没有冲突，但是比第二个红色的时间结束时间晚。因此，第二个红色被选上，黑色的没选上。 无论哪一种情况，这些区间总有一部分与不重叠区间的尾部重叠。因此只要这些箭从不重叠区间的尾巴这个地方穿过去，就能把这些区间射穿。
【代码】
【结果】
|