信息学奥赛一本通 1323：【例6.5】活动选择 | 洛谷 P1803 凌乱的yyy / 线段覆盖

ybt 1323：【例6.5】活动选择
洛谷 P1803 凌乱的yyy / 线段覆盖
注意：ybt 1323数据个数最大为 1 0 3 10^3 103， 洛谷P1803数据个数最大为 1 0 6 10^6 106

要想证明贪心选择可以得到最优解，只需要证明最优解包含每一次的贪心选择。
使用数学归纳法：

证明最优解包含第一次的贪心选择假设存在最优解包含前k次的贪心选择，证明该最优解包含第k+1次的贪心选择

贪心选择：每次选择不与已选择活动重叠的结束时间最早的活动

证明：存在最优的活动选择方案包含第一次贪心选择：结束时间最早的活动g

使用反证法：假设所有最优解都不包含结束时间最早的活动g
对于某一最优解，活动序列按结束时间排序为： a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1​,a2​,...,an​，显然其中没有活动g。如果将活动 g g g替换活动 a 1 a_1 a1​，由于 g g g的结束时间比 a 1 a_1 a1​早，不会与后面的活动发生重叠。活动选择方案为 g , a 2 , a 3 , . . . , a n g, a_2,a_3, ..., a_n g,a2​,a3​,...,an​，该方案中的活动数量与先前的方案的活动数量相同。先前的方案是活动数量最多的最优解，那么这个方案也是最优解，而这个方案中包含了活动g，这与假设相悖。因而原命题得证。

证明：在k次贪心选择后，存在最优的活动选择方案包含第k+1次的贪心选择：不与前面重叠的结束时间最早的活动g。

使用反证法：假设所有最优解都不包含活动g
对于某一最优解，活动序列按结束时间排序为： a 1 , a 2 , . . . , a k , a k + 1 , a k + 2 , . . . , a n a_1,a_2,...,a_k,a_{k+1}, a_{k+2}, ..., a_n a1​,a2​,...,ak​,ak+1​,ak+2​,...,an​，前k个活动是通过贪心选择得到的。
根据活动g的定义，活动g的结束时间一定早于活动 a k + 1 a_{k+1} ak+1​的结束时间，而且不与 a k a_k ak​重叠。
如果用活动g替换活动 a k + 1 a_{k+1} ak+1​，那么活动方案 a 1 , a 2 , . . . , a k , g , a k + 2 , . . . , a n a_1,a_2,...,a_k, g, a_{k+2}, ..., a_n a1​,a2​,...,ak​,g,ak+2​,...,an​的活动数量与原方案是一样的，原方案是活动数量最多的最优解，替换后的方案同样也是最优解，其中包含活动g，这与假设相悖。因而原命题得证。

用结构体对象存储各个活动的开始和结束时间。按活动的结束时间对活动进行升序排序。顺序取各个活动，只要该活动与前一个选择的活动不重叠（即该活动的起始时间不早于已经选择的最后一个活动的结束时间），那么就选择该活动。统计活动数量。

注意：ybt 1323中，数组长度N可以设为1005， 洛谷P1803数组长度N必须设为1000005

#include
using namespace std;
#define N 1000005
int b[N], e[N];
struct Act
{
    int begin, end;
};
Act act[N];
bool cmp(Act a, Act b)
{
    return a.end < b.end;
}
int main()
{
    int n, actNum = 0, lastAct = 0;//lastAct:当前已经选择的活动中最后一个活动 
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d %d", &act[i].begin, &act[i].end);
    sort(act+1, act+1+n, cmp);//按照结束时间从小到大排序 
    for(int i = 1; i <= n; ++i)
    {
        if(act[i].begin >= act[lastAct].end)//如果第i个活动在当前最后的活动后面开始 
        {
            actNum++;//选择第i活动 活动数量加1 
            lastAct = i;
        }
    }
    printf("%d", actNum);
    return 0;
}