Skip to content

Instantly share code, notes, and snippets.

@afcapel
Last active October 10, 2017 12:56
Show Gist options
  • Save afcapel/c37bb8c3eef4d8ca81378af963548e74 to your computer and use it in GitHub Desktop.
Save afcapel/c37bb8c3eef4d8ca81378af963548e74 to your computer and use it in GitHub Desktop.
# Returns whether a can be split in max_blocks with a
# max sum equal or lower to max_sum
def can_split_in_blocks?(a, max_sum, max_blocks)
n_blocks = 0
current_block_sum = 0
a.each_with_index do |elm, i|
if current_block_sum + elm <= max_sum && i > 0
# Use the current block
current_block_sum += elm
else
# Start a new block
n_blocks += 1
current_block_sum = elm
end
end
n_blocks <= max_blocks
end
def solution(k, m, a)
result_lower_bound = a.max
result_upper_bound = a.inject(&:+)
return result_upper_bound if k == 1
return result_lower_bound if k >= a.size
candidates = (result_lower_bound..result_upper_bound).to_a
result = candidates.bsearch do |c|
can_split_in_blocks?(a, c, k)
end
result
end
require 'minitest/autorun'
class Tests < MiniTest::Unit::TestCase
def test_can_split_in_blocks
assert_equal true, can_split_in_blocks?([2, 1, 5, 1, 2, 2, 2], 6, 3)
end
def test_can_not_split_in_blocks
assert_equal false, can_split_in_blocks?([2, 1, 5, 1, 2, 2, 2], 5, 3)
end
def test_example_input
assert_equal 6, solution(3, 5, [2, 1, 5, 1, 2, 2, 2])
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment