Solutions

:::info DP 解法
设 Greedy Method - 图2 是完全处于（起始时间都在其间） Greedy Method - 图3 结束以后到 Greedy Method - 图4 开始之前的集合，设 Greedy Method - 图5 是 Greedy Method - 图6 中最多容纳的活动。
我们定义最优子结构为：从 Greedy Method - 图7 中选出 Greedy Method - 图8 ， Greedy Method - 图9 和 Greedy Method - 图10 也有最多的相容活动。
状态状态转移方程为：
Greedy Method - 图11
复杂度为 Greedy Method - 图12 。 ::: :::info 贪心解法

复杂度为 Greedy Method - 图15 :::

Theorem

Thinking

不采取之前二分的做法而是从左到右的来计算。 Greedy Method - 图18 表示从 Greedy Method - 图19 到 Greedy Method - 图20 这些活动中最多能容纳的数量， Greedy Method - 图21 表示距离 Greedy Method - 图22 最近的与其相容的活动（也即 Greedy Method - 图23 前最晚结束的活动），因此我们的选择是放入（会导致一些之前被放入的活动被踢出去）或者不放入 Greedy Method - 图24 ，在这两种选择中取最大。

如果有权重，贪心就没办法做了，因为考虑不了权重。