本文共 1422 字，大约阅读时间需要 4 分钟。

• 内存限制:64MB 时间限制:1000ms

题目描述:

家住非洲的小孩，都很黑。为什么呢？

输入描述:

多组数据第一行一个0
   
    <=100。接下来n行，每行一个时间段。H1H1:M1M1-H2H2:M2M2，24小时制。保证该时间段是在一天之内的。但是，不保证，H1H1:M1M1先于H2H2:M2M2。
   

输出描述:

题目描述，“澡”神最少需要开启和关闭多少次水龙头呢？

样例输入:

1

00:12-12:12

3

00:12-13:14

13:13-18:00

17:00-19:14

样例输出:

1

2

提示:

Ps：开启和关闭为一次

解题思路:

选择不相交区间问题：贪心思想，先按b从小到大进行排序，再选择b0作为选点temp，如果出现ai>temp，则以bi作为temp，再按照这样的方式迭代，直至所有区间遍历完。这道题有点坑，输入的时候要判断两个时间点的大小。

#include 
   
    #include 
    
     using namespace std;struct edge {    int l, r;}e[110];int cmp(edge a, edge b) {    return a.r < b.r;}int main(){    char a;    int temp, ans;    int t, n, h1, h2, m1, m2;    while (cin >> n)    {        ans = 1;        for (int i = 0; i < n; i++)        {            cin >> h1 >> a >> m1 >> a >> h2 >> a >> m2;            e[i].l = h1 * 60 + m1;            e[i].r = h2 * 60 + m2;            if (e[i].l > e[i].r)                swap(e[i].l, e[i].r);        }        sort(e, e + n, cmp);        temp = e[0].r;        for (int i = 0; i < n; i++)        {            if (temp < e[i].l)            {                temp = e[i].r;                ans++;            }        }        cout << ans << endl;    }    return 0;}
    
   

转载地址：https://lzyws739307453.blog.csdn.net/article/details/84072611 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！