学步园

【作者：孟祥月  博客：http://blog.csdn.net/mengxiangyue】

有n个活动需要同时占用同一个资源，比如演讲会场，在同一时间只有一个活动能够使用这一资源。每个活动都有起始时间，按照一定的顺序安排使活动安排最优。

这个可以使用贪心算法解决，先按照活动的结束时间不递减排序，然后按照这个顺序依次安排活动，最后安排的结果是最优的。

算法比较容易，但是用Ruby写的，第一次写程序，还挺好玩的，拿出来分享一下。

#  encoding=GBK  表示使用GBK编码
#创建活动类
class Huodong
	def initialize(n,s,f)
		#定义三个实例变量
		@num = n
		@first = s
		@second = f
	end
	attr_reader :first,:second#定义了两个方法
	def <=>(other)#用于排序时候自动调用
		@second > other.second ? 1 :(@sencod ==other.second ? 0 :-1)
	end
	def to_s
		"序号是：#{@num}，开始时间是：#{@first},结束时间：#{@second}"
	end
end
#将活动的实例放到一个数组中
a = [Huodong.new(1,1,4),
	 Huodong.new(2,3,5),
	 Huodong.new(3,0,6),
	 Huodong.new(4,5,7),
	 Huodong.new(5,3,8),
	 Huodong.new(6,5,9),
	 Huodong.new(7,6,10),
	 Huodong.new(8,8,11),
	 Huodong.new(9,8,12),
	 Huodong.new(10,2,13),
	 Huodong.new(11,12,14)]
b = a.sort
result = Array.new
i = 0
finished = 0
while i < b.size
	if i == 0 
		finished = b[0].second
		result.push(b[0])
	end
	if finished<=b[i].first && i != 0
		result.push(b[i])
		finished = b[i].second
	end
	i += 1
end
puts "结果"
puts result

第一次写这个，还挺好玩，写的不好，哈哈，凑合着看吧。