题目描述
设有个n活动的集合E={1,2,..,n},其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间s_i 和一个结束时间f_i,且s_i < f_is 。如果选择了活动i,则它在时间区间 [ s_i , f_i )
)内占用资源。若区间[ s_i , f_i ) 与区间[ s_j , f_j )不相交,则称活动i与活动j是相容的。也就是说,当f_j≤ s_j或 f_j ≤s_i时,活动i与活动j相容。选择出由互相兼容的活动组成的最大集合。
输入描述:
第一行一个整数n
接下来的n行,每行两个整数s_i和f_i。
输出描述:
输出互相兼容的最大活动个数。
思路:
经典的贪心区间问题,一般这种问题我都会用pair<>来存线段的起点与终点。输入然后就是排序,再用一个数存前一个数的终点,然后去比较。
完整C++版AC代码:
#include <iostream> #include <algorithm> using namespace std; typedef pair<int, int> PII; const int N = 110; int n; PII p[N]; bool cmp(PII a, PII b) { return a.second > b.second; } int main() { ios::sync_with_stdio(); cin >> n; for (int i = 0; i < n; i++) cin >> p[i].first >> p[i].second; sort(p, p + n, cmp); int k = p[0].second, ans = 1; for (int i = 1; i < n; i++) { if (k <= p[i].first) { k = p[i].second; ans++; } } cout << ans << endl; return 0; }