Created
April 19, 2017 23:32
-
-
Save MichaelrMentele/9a4ae62f82a45ea973f6bab284f621fa to your computer and use it in GitHub Desktop.
Efficient waiting time computation for tickets challenge
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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