贪心算法详解

贪心算法（Greedy Algorithm）是一种常见的算法思想，其核心思想是在每一步选择中都采取当前状态下最好或最优（即最有利）的选择，从而希望最终得到全局最好或最优的解。贪心算法的特点是只考虑当前状态，不考虑以后的影响。

贪心算法的应用范围非常广泛，例如最小生成树、最短路径、背包问题等等。下面以活动安排问题为例，来详细讲解贪心算法的思想和实现过程。

问题描述：

有n个活动，每个活动都有一个开始时间和结束时间，你作为一个活动组织者需要安排这些活动的时间，保证每个活动的时间不重叠，问最多能安排多少个活动？

解题思路：

对于每个活动，我们只需要选择结束时间最早的活动，然后排除掉与该活动时间重叠的其他活动，继续选择结束时间最早的活动，直到所有活动都被选择完毕。这就是贪心算法的思想。

解题步骤：

1. 将所有活动按照结束时间从小到大排序。
2. 选择第一个活动，并将该活动的结束时间作为当前时间。
3. 遍历所有活动，选择结束时间大于等于当前时间的活动，并将该活动的结束时间作为当前时间。
4. 重复步骤3，直到遍历完所有活动。

代码实现：

def activity_selection(s, f):
    n = len(s)
    selected = []
    i = 0
    selected.append(i)
    for j in range(1, n):
        if s[j] >= f[i]:
            selected.append(j)
            i = j
    return selected

其中s是所有活动的开始时间，f是所有活动的结束时间，selected是最终选择的活动序号列表。

时间复杂度分析：

对所有活动按照结束时间排序的时间复杂度为O(nlogn)，遍历每个活动的时间复杂度为O(n)，因此总时间复杂度为O(nlogn)。

参考资料：

[1] 《算法导论》（第三版）