貪心算法專題小結——區間相關問題

貪心算法是一種高效算法，可以快速得到問題的答案。如果一個問題可以用貪心法解決，那麼它必須具備2條性質：1.具有最優子結構（即問題的最優解包含了子問題的最優解），2.具有貪心選擇性質（即可以通過做出局部最優選擇來構造全局最優）。下面總結一下基于貪心算法的區間問題。

一，選擇不相交區間

1.問題描述：數軸上有n個開區間(Ai,Bi)，選擇盡量多個區間，使得這些區間兩兩沒有公共點。 樣例輸入：n=5, (1,3),(2,5),(4,7),(6,9),(8,10)。 樣例輸出：3 (選擇第1,3,5個區間)

2.貪心政策：按照終點從小到大給區間排序，然後從第一個區間開始選擇。 3.代碼：

const int N=100000+10;
int n,s[N],t[N];

int main()
{
    while(~scanf("%d",&n))
    {
        me(s);me(t);
        for(int i=0;i<n;i++)
            scanf("%d%d",&s[i],&t[i]);
        vector<P>v;
        for(int i=0;i<n;i++)
        {
            v.push_back(P(t[i],s[i]));
        }
        sort(v.begin(),v.end());
        int ans=0;
        int t=0;
        for(int i=0;i<n;i++)
            if(t<v[i].second)
        {
            ans++;
            t=v[i].first;
        }
        printf("%d\n",ans);
    }
}
           

二，區間選點問題

1.問題描述：數軸上有n個閉區間[Ai,Bi]，取盡量少的點，使得每個區間都至少有一個點。 樣例輸入：n=5, [1,5], [8,9], [4,7], [2,6], [3,5] 樣例輸出：2 （選擇點5,9即可）

2.貪心政策：把所有區間按照B從小到大排序，如果B相同，按照A從大到小排序，每次都取第一個區間中的最後一個點。 3.代碼：

const int N=10000+10;
struct Node
{
    int L,R;
    bool operator<(const Node&rhs)const
    {
        return R<rhs.R||(R==rhs.R&&L>rhs.L);
    }
}a[N];

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        me(a);
        for(int i=0;i<n;i++)
            scanf("%d%d",&a[i].L,&a[i].R);
        sort(a,a+n);
        int ans=0,p=0;
        for(int i=0;i<n;i++)
        {
            if(p<a[i].L)
            {
                p=a[i].R;
                ans++;
            }
        }
        printf("%d\n",ans);
    }
}
           

三，區間覆寫問題

1.問題描述：數軸上有n個閉區間[Ai,Bi]，選擇盡量少的區間覆寫一條指定的線段[s,t]。 樣例輸入：n=5, [1,6], [7,13], [8,9], [4,7], [5,8]，被覆寫的區間：[5,10] 樣例輸出：2 （選擇第2,4即可完成覆寫） 2.貪心政策：首先進行預處理，把和[s,t]區間有交集的區間取出，按照A從小到大排序，如果第一個區間起點不是s，則無解；否則選擇起點在s的最長的區間，新的起點設定為該區間的終點，然後繼續重複上述過程，直到終點大于等于t結束。 3.代碼： 略