reconstruct queue by height

1 files changed, 20 insertions, 0 deletions

diff --git a/misc/queue-reconstruct-by-height/main.rb b/misc/queue-reconstruct-by-height/main.rb
new file mode 100644
index 0000000..474d18a
--- /dev/null
+++ b/misc/queue-reconstruct-by-height/main.rb
@@ -0,0 +1,20 @@
+#/usr/bin/env ruby
+
+def assert_equal(x, y)
+  raise "expected: #{x.inspect}, actual: #{y.inspect}" unless x == y
+end
+
+def reconstruct(input)
+  sorted = input.sort_by do |item|
+    [-item[0], item[1]]
+  end
+  result = []
+  sorted.each do |item|
+    result.insert(item[1], item)
+  end
+  result
+end
+
+input = [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
+output = [[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]]
+assert_equal(output, reconstruct(input))