活动安排问题贪心算法的最优子结构性质

贪心算法的最优子结构性质指的是一个问题的最优解包含其子问题的最优解。在活动安排问题中，我们可以将所有活动按照结束时间非降序排列。设 f(j) 表示最优的以活动 j 结尾的活动集合，那么最终的最优解就是 f(n)，其中 n 是活动总数。对于任意的活动 j，它要么不在最优解中，要么在最优解中，且最优解中包含了 f(j-1)。因此，问题具有最优子结构性质。

在贪心算法中，我们每次选择结束时间最早的活动，并将其加入最优解中。这样做的正确性依赖于活动按照结束时间排序后，每次选择的活动一定是所有可选活动中结束时间最早的，且这个活动的开始时间一定晚于前面已选择的活动的结束时间。这种贪心选择保证了每次选择的活动都是局部最优解，最终得到的解也是全局最优解。