wildcard problem2

p2.rb

#http://www.trywildcard.com/challenge/problem2
GENERATION = [9 , 10, 21, 20,  7, 11, 4, 15,  7,  7, 14,  5, 20, 6, 29, 8, 11, 19, 18, 22, 29, 14, 27, 17,  6, 22, 12, 18, 18, 30]
OVERHEAD =   [21, 16, 19, 26, 26,  7, 1,  8, 17, 14, 15, 25, 20, 3, 24, 5, 28,  9,  2, 14,  9, 25, 15, 13, 15,  9,  6, 20, 27, 22]
BUDGET = ARGV[0].to_i #2912

def binary_search_insert(list, obj)
  high = list.length
  low = 0
  mid = 0
  direction = -1

  while low < high
    mid = (high + low) >> 1
    direction = obj <=> list[mid][0]
    return mid if direction == 0
    high = mid if direction < 0
    low = mid + 1 if direction > 0
  end
  return direction < 0 ? -mid : -mid-1
end

time_spent = 0
final_set = 0
total_cards = GENERATION.length
sorted = []

OVERHEAD.each_with_index do |number, index|
  bindex = binary_search_insert(sorted, number)
  sorted[-bindex, 0] = [ [number, GENERATION[index]] ] if bindex < 0
  sorted[bindex, 0] = [ [number, GENERATION[index]] ] if bindex >= 0
end
puts sorted.inspect

while final_set < total_cards
  sorted.take(final_set).each do |card|
    overhead = card[0]
    generation = card[1]
    time_spent += generation + overhead * (final_set-1)
  end
  break if time_spent >= BUDGET
  final_set += 1
  time_spent = 0
end

puts "result: #{time_spent > BUDGET ? final_set - 1 : final_set}" #17