Greedy algorithm

greedy.rb

# Set cover problem

states = ['mt', 'wa', 'or', 'id', 'nv', 'ut', 'ca', 'az'].uniq
station = {}
station["kone"] = ['id', 'nv', 'ut'].uniq
station["ktwo"] = ['mt', 'wa', 'id'].uniq
station["kthree"] = ['or', 'nv', 'ca'].uniq
station["kfour"] = ['nv', 'ut'].uniq
station["kfive"] = ['ca', 'az'].uniq

final_station = []
covered = []

until states.empty?
  best_station = ''
  states_covered = []
  station.each do |index, s|
  covered = states & s
    if covered.length > states_covered.length
      best_station = index
      states_covered = covered
    end
  end
  states = states - states_covered
  final_station << best_station
end

puts final_station

# => kone
#    ktwo
#    kthree
#    kfive