task_overshoot.rb

def max_overshoot(task_table)
  @cache_result ||= {} 
  result = @cache_result[task_table]

  return result if result

  prev = 0
  prev = max_overshoot(task_table[0..-2]) if task_table.size > 1
  
  total_duration = task_table.reduce(0) {|i, s| i+s[:duration]}
  max_dead = task_table.last[:dead]
  result = total_duration - max_dead
  result = prev if result < 0
  @cache_result[task_table] = result
end

def insert_to_table(table, item)
  i = 0
  i += 1 while i < table.length && table[i][:dead] < item[:dead]
  table.insert(i, item)
end

def search(task_table)
  sorted_table = []
  task_table.each do |task_time|
    sorted_table = insert_to_table sorted_table, task_time
    p max_overshoot(sorted_table)
  end
end

n = gets.to_i
task_table = Array.new(n){ r=gets.split(" ").map!(&:to_i); {dead: r[0], duration: r[1]}} 
search(task_table)