gistfile1.rb

#!/usr/bin/env ruby

# O(nlogn) solution for the problem from the Coding Dojo at RailsCamp UK 2009
# Author: Bartosz Blimke

#Binary search in an array. I was too lazy so I adopted code from http://0xcc.net/ruby-bsearch/
class Array

  def bsearch_upper_boundary (range = 0 ... self.length, &block)
    lower  = range.first() -1
    upper = if range.exclude_end? then range.last else range.last + 1 end
    while lower + 1 != upper
      mid = ((lower + upper) / 2)
      if yield(self[mid])
        upper = mid
      else
        lower = mid
      end
    end
    return lower + 1 # outside of the matching range.
  end

end

Prediction = Struct.new(:start, :stop, :score)

class InputParser

  attr_reader :predictions

  def initialize(filename)
    @file = File.new(filename)
    skip_dna_sequences #they are not needed
    load_predictions
  end

  private

  def skip_dna_sequences
    dna_length = @file.readline.chomp.to_i
    dna_lines_count = (dna_length/80.0).ceil
    1.upto(dna_lines_count) { @file.readline }
  end

  def load_predictions
    g = @file.readline.chomp.to_i
    @predictions = (1..g).map do
      line = @file.readline.chomp
      Prediction.new(*(line.split.map{|a| a.to_i}))
    end
  end

end


class WeightedIntervalSchedulingProblemSolver

  def initialize(intervals)
    @intervals = intervals
  end

  def calculate_maximum_score
    sort_intervals_ascending_by_start_time
    @j = @intervals.map { |interval| find_index_of_next_nonoverlapping_interval_after_interval(interval) }
    calculate_maximum_partial_scores[0]
  end

  private

  def sort_intervals_ascending_by_start_time
    @intervals.sort! {|a,b| a.start <=> b.start }
  end

  def find_index_of_next_nonoverlapping_interval_after_interval(interval)
    @intervals.bsearch_upper_boundary {|j| j.start > interval.stop}
  end

  def calculate_maximum_partial_scores
    @maximum_score_for_indices_at_least = []
    (@intervals.length-1).downto(0) do |i|
      @maximum_score_for_indices_at_least[i] = calculate_maximum_score_for_indices_at_least(i)
    end
    @maximum_score_for_indices_at_least
  end

  def calculate_maximum_score_for_indices_at_least(i)
    [
      @intervals[i].score + @maximum_score_for_indices_at_least[ @j[i] ].to_i, #to_i converts nil to 0
      @maximum_score_for_indices_at_least[i+1].to_i
    ].max
  end

end


parser = InputParser.new(ARGV[0])
solver = WeightedIntervalSchedulingProblemSolver.new(parser.predictions)
p solver.calculate_maximum_score