如何实现贪心算法？

贪心算法是一种贪心策略的算法，它在每一步选择中都采取当前状态下最优的选择，从而得到全局最优解。贪心算法通常需要满足无后效性和最优子结构性质。

例题：假设有一组活动，每个活动都有开始时间和结束时间，你作为主持人希望安排尽可能多的活动，请问你最多能安排多少个活动？

分析：我们可以按照活动结束的时间从早到晚排序，每次选择结束时间最早的活动，然后将其安排在日程表上，接着从剩下的活动中选择结束时间最早的，直到所有活动都被安排完为止。这种策略的正确性在于每次选择的都是当前状态下最优的活动，因此最终得到的就是全局最优解。

Java代码实现：

public static List<Integer> greedyActivitySelection(int[] start, int[] end) {
    List<Integer> res = new ArrayList<>();
    int n = start.length;
    int lastEnd = -1;
    for (int i = 0; i < n; i++) {
        if (start[i] >= lastEnd) {
            res.add(i);
            lastEnd = end[i];
        }
    }
    return res;
}

代码分析：

• 首先定义一个长度为n的结果数组res，表示最终安排的活动的下标。
• 初始化lastEnd为-1，表示当前日程表上最后一个活动的结束时间。
• 从i = 0开始遍历所有活动，对于每个活动，如果其开始时间大于等于lastEnd，则将其加入到结果数组res中，并更新lastEnd为其结束时间。
• 最终返回结果数组res。