《入门经典》——6.28

贪心策略:选择不相交区间问题。

  抽象化描述:给出n个区间[ai,bi],从中选出尽可能多的区间,使得这些区间能够不相交。实际问题当中的应用:这个模型常常以日程安排的实际问题作为载体进行考察。

  贪心策略分析:

  首先我们应该明白的一点是,如果一个区间c是另一个区间d的子区间,那么很显然我们是不会去选区间d的。

 那么现在我们来分析整个决策过程中可能出现的情况。

 显然我们应该去分析相邻区间。给出3个区间[a1,b1]、[a2,b2]、[a3,b3],并确定区间右端点的关系为b1<b2<b3,这样使得我们得以确定一个变量来分析另一个变量。

  对于a1>a2,这是上面我们说过的包含情况。

  对于a1<a2,在这种情况下,我们再来讨论区间[a3,b3]和区间[a1,b1]的关系。

i)如果二者不相交,显然当前我们对于区间1和区间2,必然选择区间1.可能有人会问为什么不去讨论区间3和区间2的关系?显然这里必然讨论区间3和区间2相交,不然的话整个情况就没有讨论的意义。

ii)如果两者相交,这样这三个区间都有相交部分,显然我们还是选择区间1,由于其b1是最小的,所以在后面的决策(因此选择的区间的过程基于bi由小到大的排序)中,能够尽可能的为别的区间腾出空间。

  因此我们会得到贪心策略,给bi对区间进行排序,每次选择存储区间的线性表的首元素,然后删除掉该元素和与该元素有相交部分的区间。

原文地址:https://www.cnblogs.com/rhythmic/p/5627528.html