HDU 2037 今年暑假不AC（区间贪心之不相交区间）

本文主要是介绍HDU 2037 今年暑假不AC（区间贪心之不相交区间），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

description

给定每个电视节目的开始和结束时间，判断一天最多能看多少个电视节目。

Input

输入数据包含多个测试实例，每个测试实例的第一行只有一个整数n(n<=100)，表示你喜欢看的节目的总数，然后是n行数据，每行包括两个数据Ti_s,Ti_e (1<=i<=n)，分别表示第i个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。n=0表示输入结束，不做处理。

Output

对于每个测试实例，输出能完整看到的电视节目的个数，每个测试实例的输出占一行。

Sample Input

12
1 3
3 4
0 7
3 8
15 19
15 20
10 15
8 18
6 12
5 10
4 14
2 9
0

Sample Output

5

solution

经典区间贪心的不相交区间问题。题目抽象为：数轴上有n个区间[ai,bi]，要求选择尽量多个区间，使得这些区间两两没有公共点。总是选择右端最小的区间策略贪心，即先看最先结束的电视。

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
struct Show
{int s, e;bool operator<(Show t){return e < t.e;}
};
Show show[111];
int main()
{// freopen("in.txt", "r", stdin);int N;while (scanf("%d", &N) && N != 0){for (int i = 0; i < N; i++)scanf("%d%d", &show[i].s, &show[i].e);sort(show, show + N);int current_time = 0, ans = 0;for (int i = 0; i < N; i++){if (show[i].s >= current_time){current_time = show[i].e;ans++;}}printf("%d\n", ans);}return 0;
}

这篇关于HDU 2037 今年暑假不AC（区间贪心之不相交区间）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---