HDU 2037 今年暑假不AC （貪心）

HDU 2037 今年暑假不AC （貪心）

非常經典的活動安排問題變形， 與算法教材的活動安排一樣，根據結束時間進行排序，然後相容的累加即可。

// 經典貪心問題  活動時間安排的簡單變形
// 按活動結束時間，遞增排序， 結束時間早的，優先選擇

#include 

using namespace std;

typedef struct active
{
    int st;
    int ed;
    bool operator < (const struct active &at) const
    {
        return this->ed < at.ed;
    }
}Active;

const int MAX = 100+5;
Active arr[MAX];

int main(void)
{
    //freopen(in.txt, r, stdin);

    int n = 0;
    while(cin>>n && n != 0)
    {
        for(int i=0; i= arr[j].ed)
            {
                j = i;
                cnt++;
            }
        }

        printf(%d
, cnt);
    }

    return 0;
}