今年暑假不AC

hdoj 2037

贪心算法--活动安排问题模型

使用贪心算法的关键是证明可以设用贪心：

设E={1,2,3,...n}为所给出的活动的集合，  设集合A为原问题的最优解 ，由于按照活动结束时间已经排好序，所以第一个活动具有最早结束时间，将1加入集合A中，原问题将转化为对E中所有与活动1相容的活动进行安排的子问题， 并且E中最早的开始时间必须大于等于A中最晚结束时间，将原问题的规模缩小了，这样可以迭代的进行，A中最晚的结束时间是最后加入的活动的结束时间。

#include <iostream>
#include <algorithm>
#include <bitset>
using namespace std;
struct node
{
    int beg,end;
};
node Time[105];
int n;
bool operator <(const node &a,const node &b)
{
    return a.end<b.end;
}

void greedySelect()
{
    bitset<105> b;
    sort(Time,Time+n);
    b.reset();
    int j=0;
    b[j]=1;
    for(int i=1;i<n;i++)
    {
        if(Time[i].beg>=Time[j].end)
        {
            b[i]=1;
            j=i;
        }
    } 
    cout<<b.count()<<endl;
}
int main()
{
    while(cin>>n,n)
    {
        for(int i=0;i<n;i++)
            cin>>Time[i].beg>>Time[i].end;
         greedySelect();
    }
        
    system("pause");
    return 0;
}