Elevator Requests IV - Video Solutions

Problem Overview: You're given a set of elevator requests, each with a start floor, destination floor, and time, and you need to schedule a set of elevators to minimize the total waiting time or completion time. The optimal solution must efficiently assign requests to elevators while respecting their movement constraints.

Approach 1: Brute Force (O(n^2) time, O(1) space)

Simulate every possible assignment of requests to elevators. For each request, try all elevators and check which one finishes earliest based on current position and direction. This works for tiny inputs but explodes as n grows because you iterate through all elevators for every request. It's a good starting point to verify correctness but never passes large test cases.

Approach 2: Greedy with Sorting (O(n log n) time, O(n) space)

Sort requests by arrival time and process them in order. Maintain each elevator's current floor and next available time. For each request, pick the elevator that can reach the start floor earliest (considering travel time from its current position). This is a classic greedy strategy for interval scheduling and often passes most test cases. The key insight is that you only need to compare the earliest available elevator—no need to try all combinations. However, it fails when future requests could be better served by waiting for a closer elevator, so it's not optimal in all cases.

Approach 3: Optimal with Priority Queue (O(n log n) time, O(n) space)

Use a min-heap to track each elevator's ready time and the request they're handling. Instead of scanning all elevators, you pop the elevator with the earliest available time and assign the current request to it, then push it back with its new availability. This gives a globally optimal schedule when the cost function is additive and each request is independent. The trick is to treat the elevator as a resource that becomes free after serving a request, and the heap keeps the next free elevator at the top. This approach is what interviewers expect—it shows you understand priority queues and greedy scheduling.

Recommended for interviews: The optimal priority queue solution is the one to present. Brute force shows you can reason about the problem structure, but the heap-based method demonstrates you can apply classic algorithms (greedy + priority queue) to real-world constraints. Start with brute force to confirm understanding, then jump to the optimal solution. Mention that the greedy solution fails for certain corner cases where a longer wait for a closer elevator beats picking the first free one, but the heap approach handles that by always choosing the earliest available elevator.

Relevant topics to strengthen your understanding: greedy algorithms, priority queues, and scheduling.