Skip to content

Instantly share code, notes, and snippets.

@MichaelrMentele
Created April 19, 2017 23:32
Show Gist options
  • Select an option

  • Save MichaelrMentele/9a4ae62f82a45ea973f6bab284f621fa to your computer and use it in GitHub Desktop.

Select an option

Save MichaelrMentele/9a4ae62f82a45ea973f6bab284f621fa to your computer and use it in GitHub Desktop.
Efficient waiting time computation for tickets challenge
def waitingTime(tickets, p)
# if you only want 1 ticket just count number of people in front,
return p + 1 if tickets[p] == 1
wait = 0
multiplier = 1
for i in 0...tickets.length do
next if i == p
# if the person eventually drops off, they will only add the
# number of tickets they are buying
if tickets[i] < tickets[p]
wait += tickets[i]
elsif tickets[i] >= tickets[p]
# person who wants more tickets is in back, so on the final
# run he won't add any time
if i > p
wait -= 1
end
# Since the person is always in the queue, he adds 1 for each
# time through the queue, in this case tickets[p] times
multiplier += 1
end
end
# total wait
wait + tickets[p] * multiplier
end
# Me figuring out the algorithm...
puts waitingTime([1, 2, 3, 7, 5], 4) == 16 # 5*2 + 6
puts waitingTime([5, 1, 2, 3, 7], 0) == 15 # 5*2 - 1 + 6
puts waitingTime([5, 1, 2, 3, 7], 1) == 2 # 2
puts waitingTime([5, 10, 2, 3, 7], 1) == 27 # 10 + 5 + 5 + 7 = 27
puts waitingTime([5, 10, 2, 3, 7], 3) == 13 # 3*4 - 1 + 2
puts waitingTime([5, 10, 2, 3, 7], 4) == 24 # 7*2 + 10
puts waitingTime([5, 10, 2, 3, 10], 4) == 30 # 7*2 + 10
# testing different cases...
puts waitingTime([10], 0) == 10
puts waitingTime([1], 0) == 1
puts waitingTime([1, 2, 3, 4, 10], 4) == 20
puts waitingTime([1, 2, 3, 4, 1], 4) == 5
puts waitingTime([2, 2, 2, 2, 2], 4) == 10
puts waitingTime([3, 3, 3, 3, 2], 4) == 10
puts waitingTime([3, 3, 2, 3, 3], 2) == 8
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment