算法之贪心

[code="java"]def greedySelector(n,a,b)
  b[0]=true
   j=0
   for i in 1..n-1
     if(a[i][0]>=a[j][1])
       b[i]=true
       j=i
     else
       a[i]=false
     end
   end
  c=b.select{|x|x==true}.size
end
a=[[1,23],[12,28],[25,35],[27,80],[36,50]]

p a.sort!{ |x,y|x[1]<=>y[1}
b=[]
n=a.size
p greedySelector(n,a,b)

  活动安排问题是可以用贪心算法有效求解的一个很好的例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供一个简单漂亮的方法，是尽可能多的活动能兼容的使用公共资源。
  当然这个问题也可以采用另外一种更为高效的算法，当然没有采用贪心策略。将n个活动1..n看做实直线上的n个半闭活动区域[s[i],f[i])，所讨论的问题实际上时求这n个半闭区间的最大重叠数