Skip to content

Instantly share code, notes, and snippets.

@bblimke
Created October 23, 2009 08:55
Show Gist options
  • Save bblimke/216759 to your computer and use it in GitHub Desktop.
Save bblimke/216759 to your computer and use it in GitHub Desktop.
#!/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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment