设有n个活动的集合E=1 2 … n其中每个活动都要求使用同一资源而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi且si fi 。如果选择了活动i则它在半开时间区间si fi内占用资源。若区间si fi与区间sj fj不相交则称活动i与活动j是相容的。随机生成n个任务n=81632…用贪心法求近似解画出执行时间随n的变化曲线。给出正确运行代

以下是使用贪心法求解活动选择问题的代码：

def activity_selection(start, finish):
    n = len(start)
    selected_activities = []
    
    # 将活动按照结束时间从早到晚排序
    activities = sorted(zip(start, finish), key=lambda x: x[1])
    
    # 选择第一个活动
    selected_activities.append(activities[0])
    
    # 遍历剩下的活动
    for i in range(1, n):
        # 如果当前活动的开始时间晚于已选择活动的结束时间，则选择该活动
        if activities[i][0] >= selected_activities[-1][1]:
            selected_activities.append(activities[i])
    
    return selected_activities

# 测试
start = [1, 3, 0, 5, 8, 5]
finish = [2, 4, 6, 7, 9, 9]
selected = activity_selection(start, finish)
print("选择的活动：", selected)

执行结果：

选择的活动： [(1, 2), (3, 4), (5, 7), (8, 9)]

对于生成随机任务并绘制执行时间随n的变化曲线，可以使用以下代码：

import random
import matplotlib.pyplot as plt
import time

def generate_random_tasks(n):
    start = [random.randint(0, 100) for _ in range(n)]
    finish = [start[i] + random.randint(1, 10) for i in range(n)]
    return start, finish

def plot_execution_time():
    n_values = [8, 16, 32, 64, 128, 256]
    execution_times = []
    
    for n in n_values:
        start, finish = generate_random_tasks(n)
        
        start_time = time.time()
        activity_selection(start, finish)
        end_time = time.time()
        
        execution_time = end_time - start_time
        execution_times.append(execution_time)
    
    plt.plot(n_values, execution_times)
    plt.xlabel('Number of tasks')
    plt.ylabel('Execution time (s)')
    plt.title('Execution time vs Number of tasks')
    plt.show()

# 绘制执行时间随n的变化曲线
plot_execution_time()

执行结果将会显示一个关于执行时间随任务数量增加的变化曲线。