Python实现贪心算法解决活动安排问题详解

温以宁

发布时间：2026-10-13 | 2人浏览过

原创

本文深入解析Python中贪心算法在解决活动安排问题中的应用。通过按结束时间排序并迭代选择相容活动，实现最大活动数量计算。文章提供完整的冒泡排序与贪心选择代码示例，详细阐述局部最优到全局最优的转化逻辑及代码执行流程，帮助开发者掌握区间调度算法的核心实现。

贪心算法

其核心原理在于求解过程中，始终选取当前状态下最优的选项。这意味着该算法并不追求整体全局最优，而是基于某种标准寻求局部最优解。尽管贪心算法无法保证对所有问题都能得出整体最优解，但在广泛的问题领域中，它往往能生成整体最优解或其近似解。

该算法具备自顶向下、迭代执行的特征，通过连续进行贪心选择，将原问题逐步简化为规模更小的子问题。每一步选择旨在获取局部最优解，但由此累积的全局解未必总是最优，因此贪心策略通常不涉及回溯。适用于贪心算法的问题通常具备两个关键特性：贪心选择性质与最优子结构性质。

具体问题场景为：给定一组活动及其对应的开始与结束时间，目标是计算出能够参与的最大活动数量，或者确定这些活动的具体起止时间。

贪心算法的具体解决思路如下：

首先使用两个数组分别存储活动的开始与结束时间。依据活动的结束时间对活动序列进行非递减排序，同时同步调整开始时间列表。文中示例采用冒泡排序法实现同步交换，例如对于活动序列（1,4）、（2,3）、（3,5），排序后得到的结果将用于后续处理。

s = [2,1,3] 
f = [3,4,5]

接下来，通过比较下一个活动的开始时间与上一个已选活动的结束时间，判断两者是否相容。若开始时间大于或等于上一个活动的结束时间，则判定为相容，否则不相容。具体实现代码如下：

#用冒泡排序对结束时间进行排序，同时得到对应的开始时间的list
def bubble_sort(s,f):
  for i in range(len(f)):
    for j in range(0,len(f)-i-1):
      if f[j] > f[j+1]:
        f[j], f[j+1] = f[j+1],f[j]
        s[j],s[j+1] = s[j+1],s[j]
  return s,f

def greedy(s,f,n):
  a = [True for x in range(n)]
  #初始选择第一个活动
  j = 0
  for i in range(1,n):
    #如果下一个活动的开始时间大于等于上个活动的结束时间
    if s[i] >= f[j]:
      a[i] = True
      j = i
    else:
      a[i] = False
  return a

n = int(input())
arr = input().split()
s = []
f = []
for ar in arr:
  ar = ar[1:-1]
  start = int(ar.split(',')[0])
  end = int(ar.split(',')[1])
  s.append(start)
  f.append(end)

s,f = bubble_sort(s,f)
A = greedy(s,f,n)

res = []
for k in range(len(A)):
  if A[k]:
    res.append('({},{})'.format(s[k],f[k]))
print(' '.join(res))

代码执行结果展示：输入包含11个活动的起止时间数据，程序输出所有相容活动的具体起止时间。