Skip to content

Instantly share code, notes, and snippets.

@ClayShentrup
Last active January 31, 2020 22:17
Show Gist options
  • Save ClayShentrup/06237c34322694006f37c6fcae022d04 to your computer and use it in GitHub Desktop.
Save ClayShentrup/06237c34322694006f37c6fcae022d04 to your computer and use it in GitHub Desktop.
Calculate number of days at least one employee is working
# frozen_string_literal: true
class DaysBinarySearchTree
attr_reader(:sum)
def initialize
@sum = 0
end
def size
@root.sum
end
def insert(first_day, last_day)
node = DayRangeNode.new(first_day, last_day)
if @root
@root.insert(node)
else
@root = node
end
end
end
class DayRangeNode
def initialize(first_day, last_day)
@first_day = first_day
@last_day = last_day
end
def insert(node)
return insert_left(node) if precedes_me?(node)
return insert_right(node) if follows_me?(node)
merge(node)
collapse(node)
end
def collapse(node)
if @left
@left.collapse(node)
if touches?(@left)
merge(@left)
@left = @left.left
end
end
if @right
@right.collapse(node)
if touches?(@right)
merge(@right)
@right = @right.right
end
end
end
def touches?(node)
!(precedes_me?(node) || follows_me?(node))
end
def sum
left_sum + size + right_sum
end
def size
last_day - first_day + 1
end
def to_s
"#{first_day}-#{last_day}"
end
def inspect
"(#{first_day}-#{last_day} (LEFT:(#{@left.inspect}), RIGHT:(#{@right.inspect}))"
end
protected
attr_reader(:first_day, :last_day, :left, :right)
private
def left_sum
@left ? @left.sum : 0
end
def right_sum
@right ? @right.sum : 0
end
def precedes_me?(node)
node.last_day < first_day - 1
end
def follows_me?(node)
node.first_day > last_day + 1
end
def insert_left(node)
if @left
@left.insert(node)
else
@left = node
end
end
def insert_right(node)
if @right
@right.insert(node)
else
@right = node
end
end
def merge(node)
@first_day = [first_day, node.first_day].min
@last_day = [last_day, node.last_day].max
end
end
def sum_of_days(employees)
d = DaysBinarySearchTree.new
employees.each do |employee|
employee.each do |day_range|
d.insert(*day_range)
end
end
puts d.size
end
puts sum_of_days([[[0, 5], [7, 10]], [[3, 4]]]) # 10
puts sum_of_days([[[0, 5], [7, 10]], [[3, 4], [12, 16]]]) # 15
puts sum_of_days([[[0, 5], [7, 10]], [[3, 4], [12, 16], [6, 6]]]) # 16
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment