贪心算法之区间覆盖有关问题

贪心算法之区间覆盖问题

问题描述:用i表示x轴上坐标为[i-1,i]的区间(区间长度为1),并给出M个不同的整数来表示M个这样的区间。现在要求画出几条线段覆盖住所有的区间,条件是:每条线段可任意长,但要求所画线段长度之和最小,并且线段的数目不超过N

举例:给出M=61,2,4,5,7,11,分别表示6个长度为1的区间,要求用不超过N=3条线段将其覆盖。

 

贪心算法之区间覆盖有关问题

上图给出了一种可行的覆盖方案,用三段长线段覆盖住6个长度为1的小线段,使得3短线段长度之和最小


例如:M=5,整数1、3、4、8、11表示区间。
    要求:所用线段不超过 N=3条。

贪心算法之区间覆盖有关问题



分析
    1) 整型数组p[M]表示所有从0开始的区间长度,假设p[M]已经
按从小到大的顺序排好


    2) 如果N>=M,
那么用 M条长度为 1 的线段可以覆盖住所有的区间,所求的线段总长为 M;


3)如果N<M,可以按照如下的贪心准则解决:


① 如果N=1,即要用一条线段覆盖住所有区间。


      线段总长:p[M-1]-p[0]+1。


贪心算法之区间覆盖有关问题


其中:p[0]=1  ,  p[1]=3  ,   p[2]=4 , ……,p[M-1]=M--区间总长度


② 如果N=2,即要用 2 条线段覆盖住所有区间,相当于把N=1中的线段分为两部分,各覆盖左、右区间。


如果线段在M个区间中不相邻的区间之间断开(如在p[0]与p[1]之间),这样总长度小于断开之前。【不相邻的很多怎么办?】


线段总长度减少: p[1]-p[0]-1


贪心算法之区间覆盖有关问题


回顾我们的题目要求:求最小线段总长。



找到间隔最大的两个相邻区间,将之断开。


   这一过程相当于找:d[i]=p[i]-p[i-1]-1(1<i<M)的最大值



如果N=3,相当于在N=2的方案下,将某条线段断成两截,并作可能的端点调整。


为了得到当前情况下最小的总长度,同样应该在间隔最大的两个相邻区间之间断开


    如果原来的方案是N=2时总长最小的方案,这一操作是N=3时总长最小的方案。



当N=k(k>1)时依此类推,只需在N=k-1时最小总长的覆盖方案下,找到被同一条线段覆盖的间隔最大的两个相邻区间


------“贪心”地从间隔处断开并调整两边线段的端点,就可以得到总长最小的方案



贪心策略就是每次从找到当前间隔最大的相邻区间