Minimum Total Waiting Time for One Elevator
Updated
Problem statement
A building has one elevator. It starts at floor start. Person i is waiting at floor floors[i], and several people can wait on the same floor.
Everyone is already waiting at time 0 and keeps waiting until the elevator first arrives at their floor. The elevator moves one floor per unit of time, can change direction whenever it likes, and stopping takes no time. It arrives at a floor as soon as it passes it, so people on the floors it passes are reached on the way. A person on the start floor waits 0.
Choose the route that makes the total waiting time of all people as small as possible, and return that total. The elevator does not have to return anywhere, and what the people do after they are reached does not matter.
Function
minimumTotalWait(start: int, floors: int[]) → longExamples
Example 1
start = 10floors = [8,13,13,13]return = 17The elevator starts at floor 10. If it goes to floor 13 first, it arrives at time 3, where three people wait, so they wait 3 + 3 + 3 = 9 in total. Then it goes down to floor 8, which takes 5 more units, so it arrives at time 8 and that person waits 8. The total is 9 + 8 = 17. Going to floor 8 first is worse: that person waits 2, but the three people at floor 13 each wait 2 + 5 = 7, so the total is 2 + 21 = 23. The answer is 17.
Example 2
start = 4floors = [4,1,9]return = 14The person at floor 4 is reached at time 0. Going down first, the elevator reaches floor 1 at time 3 and floor 9 at time 3 + 8 = 11, so the total is 0 + 3 + 11 = 14. Going up first, it reaches floor 9 at time 5 and floor 1 at time 5 + 8 = 13, so the total is 0 + 13 + 5 = 18. The answer is 14.
Example 3
start = 1floors = [5,3,4]return = 9The elevator only needs to go up. It passes floor 3 at time 2, floor 4 at time 3 and reaches floor 5 at time 4. The waiting times are 2, 3 and 4 in some order, and the total is 9. The people do not need to be listed in the order of the floors.
Constraints
1 <= floors.length <= 20001 <= floors[i] <= 1091 <= start <= 109
More Expedia Onsite Interview questions
- Scramble StringONSITE INTERVIEW · Seen Sep 2026
- Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
- Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
- Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
- Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
- Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
- Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
- Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
- Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
- Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024
Similar questions at other companies
- Russian Doll EnvelopesGoogle · ONSITE INTERVIEWGoogle interview questions
- Russian Doll EnvelopesInMobi · ONSITE INTERVIEWInMobi interview questions
- Russian Doll EnvelopesAirbnb · ONSITE INTERVIEWAirbnb interview questions
- Maximum Length Pair ChainAmazon · ONSITE INTERVIEW
- Maximum Total Length of Non-Overlapping IntervalsBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
- Cheapest Order to Cut a RodAdobe · PHONE SCREENAdobe interview questions
- Maximum Escape Game ScoreMicrosoft · OAMicrosoft interview questions
- Maximum Taxi EarningsWells Fargo · OAWells Fargo interview questions
- Recursive Display SortFigma · PHONE SCREEN · ONSITE INTERVIEWFigma interview questions
- Allocate Mailboxes with Squared DistanceLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
Expedia interview experiences
- Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
- Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
- Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
- Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
- Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)
- Expedia SWE Intern Final Round: 126 Experiences (Part 1 of 6)