假设要在足够多的会场里安排一批活动,并希望使用尽可能少的会场。设计一个有效的 贪心算法进行安排。
输入格式:
第一行有 1 个正整数k,表示有 k个待安排的活动。 接下来的 k行中,每行有 2个正整数,分别表示 k个待安排的活动开始时间和结束时间。时间 以 0 点开始的分钟计。
输出格式:
输出最少会场数。
输入样例:
5
1 23
12 28
25 35
27 80
36 50
输出样例:
在这里给出相应的输出。例如:
3
我的代码如下:
#!/usr/bin/python
# -*- coding:utf-8 -*-
n = eval(input())
list = []
for i in range(0, n):
list.append(input().split(" "))
list.sort(key=lambda y: y[0])
# s保存开始时间,f保存结束时间
s = [eval(list[i][0]) for i in range(n)]
f = [eval(list[i][1]) for i in range(n)]
# for i in range(n-1):
# for j in range(i+1,n):
# if s[i]>s[j]:
# f[i],f[j]=f[j],f[i]
# s[i], s[j] = s[j], s[i]
print(s)
print(f)
sign = [False for i in range(n)]
# 已经安排的场次
count = 0
# 总安排的场次
sum = 0
while n-count > 0:
cur = 0
for i in range(n):
if s[i] >=cur and sign[i] == False:
sign[i] = True
cur = f[i]
count += 1
sum = sum+1
print(sum)
问题是用sort结果不对,用双层for循环,最后运行结果正确,求解惑!
用sort在oj平台的错误提示如下: