import randomimport timeimport numpy as npimport matplotlibpyplot as pltdef generate_activitiesn # 生成n个活动的起始时间和结束时间 activities = for i in rangen start_time = randomrandint0 100 e

上述代码实现了贪心算法和动态规划算法来解决活动选择问题。

贪心算法的实现如下：

1. 首先生成n个活动的起始时间和结束时间。
2. 将活动列表按照结束时间进行排序。
3. 初始化一个空的选中活动列表和一个变量current_end_time表示当前活动的结束时间。
4. 遍历排序后的活动列表，如果当前活动的起始时间大于等于current_end_time，则将该活动加入选中活动列表，并更新current_end_time为该活动的结束时间。
5. 返回选中的活动列表。

动态规划算法的实现如下：

1. 首先生成n个活动的起始时间和结束时间。
2. 将活动列表按照结束时间进行排序。
3. 初始化一个长度为n的dp数组，用于记录每个活动的最大兼容子集大小，初始值都为1。
4. 使用两层循环遍历活动列表，如果活动i的起始时间大于等于活动j的结束时间，则活动i可以加入活动j的最大兼容子集，更新dp[i]为dp[j]+1和dp[i]中大的一个。
5. 找到dp数组中的最大值max_activities，表示最大兼容子集的大小。
6. 初始化一个空的选中活动列表和一个变量current_end_time表示当前活动的结束时间。
7. 倒序遍历dp数组，如果活动i的最大兼容子集大小等于max_activities，并且活动i的结束时间大于等于current_end_time，则选中该活动，并更新current_end_time为该活动的起始时间，max_activities减1。
8. 返回选中的活动列表，按照起始时间升序排序。

compare_execution_time函数用于比较贪心算法和动态规划算法在不同活动数量下的执行时间。首先生成不同数量的活动，然后分别调用贪心算法和动态规划算法计算选中的活动，并记录执行时间。最后使用多项式拟合对执行时间进行平滑处理，并绘制两种算法的执行时间曲线。