Skip to content

Instantly share code, notes, and snippets.

@felipernb
Created October 19, 2012 12:39
Show Gist options
  • Save felipernb/3918046 to your computer and use it in GitHub Desktop.
Save felipernb/3918046 to your computer and use it in GitHub Desktop.
Skyline problem in Ruby
#http://acm.uva.es/p/v1/105.html
buildings = [[1,11,5], [2,6,7], [3,13,9], [12,7,16], [14,3,25], [19,18,22], [23,13,29], [24,4,28]]
def skyline(buildings)
#initialize the skyline setting 0 in all points
line_size = 0
buildings.each {|b| line_size = [line_size, b[2]].max}
line = Array.new(line_size+1).fill(0)
buildings.each {|b| (b[0]..b[2]-1).each {|x| line[x] = [line[x], b[1]].max}}
skyline = []
curr_height = 0
line.each_with_index do |y, x|
if y != curr_height
skyline << [x,y]
curr_height = y
end
end
return skyline
end
puts skyline(buildings).inspect
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment