实验10相容问题

问题：

有n项活动申请使用同一个礼堂，每项活动有一个开始时间和一个截止时间。如果任何两个活动不能同时举行，问如何选择这些活动，从而使得被安排的活动数量达到最多。

解析：

如果我们选择开始时间最早的节目，得不到最优解

如果我们选择时间最短的节目，也无法得到最优解

可以用数学归纳法证明，我们的贪心策略应该是每次选取结束时间最早的活动。

直观上也很好理解，按这种方法选择相容活动为未安排活动留下尽可能多的时间。

所以，我们的贪心策略是按照节目的结束时间排序。

设计（核心代码）：

bool cmp(const node &a,const node &b)
{
    return a.e<b.e;
}

sort(p + 1, p + 1 + n, cmp);
int ans = 0, tmp = -1;
for (int i = 1; i <= n; ++i)
{
    if (p[i].s >= tmp)    ans++, tmp = p[i].e;
}

分析：

复杂度：$O( n log(n) )$

源码：

https://github.com/Big-Kelly/Algorithm

#include<bits/stdc++.h>
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

#define ll long long
#define PLL pair<ll,ll>
#define PII pair<int,int>
#define bug printf("*********
")
#define FIN freopen("input.txt","r",stdin);
#define FON freopen("output.txt","w+",stdout);
#define IO ios::sync_with_stdio(false),cin.tie(0)
#define ls root<<1
#define rs root<<1|1

using namespace std;
const int inf = 0x3f3f3f3f;
const ll Inf = 1e14 + 7;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;

struct node
{
    int s, e;
}p[maxn];

bool cmp(const node& a, const node& b)
{
    return a.e < b.e;
}

int main()
{
    int n;
    while (~scanf("%d", &n), n)
    {
        for (int i = 1; i <= n; ++i)    scanf("%d %d", &p[i].s, &p[i].e);
        sort(p + 1, p + 1 + n, cmp);
        int ans = 0, tmp = -1;
        for (int i = 1; i <= n; ++i)
        {
            if (p[i].s >= tmp)    ans++, tmp = p[i].e;
        }
        printf("%d
", ans);
    }
}