尽量多参加

有很多活动，各有开始和结束时间，时间重叠的不能同时参加，问最多能参加几个。这是经典的活动选择问题。

贪心策略：把所有活动按结束时间从早到晚排序，然后从头扫，每次只要这个活动的开始时间不早于上一个已选活动的结束时间（不冲突），就选它。

struct Act { int s, e; };          // 开始、结束
sort(v, v + n, [](Act a, Act b){
    return a.e < b.e;              // 按结束时间升序
});
int cnt = 0, lastEnd = -1;
for (int i = 0; i < n; i++)
    if (v[i].s >= lastEnd) {       // 不冲突
        cnt++;
        lastEnd = v[i].e;          // 更新占用到的时间
    }

直觉是：越早结束的活动，给后面留下的时间越多。比如一个 $9$ 点结束、一个 $11$ 点结束，选 $9$ 点结束的更划算。复杂度 $O(n\log n)$，瓶颈在排序。下一节说清它为什么正确。