hdoj2037 今年暑假不AC（贪心）

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=2037

思路

想要看的节目尽可能的多，则首先要将节目按照结束时间从早到晚排序，因为一个节目越早结束，留给后面的节目的时间就越多，也就能看到更多的节目。如果按照开始时间从早到晚排序，由于节目可能持续很长时间，所以将会导致最后的结果不准确。举个例子，有三个节目（1,10），（3,5），（6,8），按开始时间从早到晚排序，则只能看1个节目（1,10），而按照结束时间从早到晚排序，则能看2个节目（3,5）和（6,8）。

代码

 #include <algorithm>

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <vector>

 using namespace std;

 struct Node

 {

     int s, e;

     Node(int s, int e):s(s), e(e) {}

     bool operator < (const Node& node) const

     {

         return e < node.e;  //将节目按照结束时间从早到晚排序

     }

 };

 vector<Node> v;

 int main()

 {

     //freopen("hdoj2037.txt", "r", stdin);

     int n;

     while(cin >> n && n)

     {

         v.clear();

         int s, e;

         for(int i=; i<n; i++)

         {

             cin >> s >> e;

             v.push_back(Node(s, e));

         }

         sort(v.begin(), v.end());

         int ans = ;

         int t = v[].e;

         for(int i=; i<n; i++)

         {

             if(v[i].s >= t)

             {

                 ans++;

                 t = v[i].e;

             }

         }

         cout << ans <<endl;

     }

     return ;

 }