Elevator Requests III - Video Solutions
Leetcode 4027 | Elevator Requests III | Leetcode weekly contest 515 | Dynamic Programming | Bitmasks
Elevator Requests III - Video Solution
Watch 2 video solutions for Elevator Requests III, a hard level problem involving Array, Dynamic Programming, Bit Manipulation. This walkthrough by CodeWithMeGuys has 175 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given an integer n denoting the number of floors in a building, where the floors are numbered from 0 to n - 1.
You are also given an integer start and a 2D integer array requests, where requests[i] = [arrivali, floori] indicates that a request for floori is made at time arrivali.
At time 0, the elevator is at floor start.
At each second, the elevator may move up by 1 floor, move down by 1 floor, or remain on its current floor.
A request can be fulfilled only at or after its arrival time; it is fulfilled instantly when the elevator is on its requested floor at any time from its arrival time onward.
Return the minimum time needed to fulfill all requests.
Example 1:
Input: n = 9, start = 0, requests = [[0,8],[6,5]]
Output: 9
Explanation:
- Move from floor 0 (
start) to floor 5 (requests[1][1]) in 5 seconds, reaching at time 5. Sincerequests[1][0] = 6, wait until time 6 to fulfill it. - Move from floor 5 to floor 8 (
requests[0][1]) in 3 seconds, fulfilling it at time 9.
Thus, all requests are fulfilled by time 9.
Example 2:
Input: n = 8, start = 5, requests = [[1,7],[7,3]]
Output: 7
Explanation:
- Move from floor 5 (
start) to floor 7 (requests[0][1]) in 2 seconds, reaching at time 2. Sincerequests[0][0] = 1has already passed, floor 7 is fulfilled at time 2. - Move from floor 7 to floor 3 (
requests[1][1]) in 4 seconds, reaching at time 6. Sincerequests[1][0] = 7, wait until time 7.
Thus, all requests are fulfilled by time 7.
Example 3:
Input: n = 7, start = 3, requests = [[0,5],[0,1],[6,3]]
Output: 8
Explanation:
- Move from floor 3 (
start) to floor 5 (requests[0][1]) in 2 seconds, fulfilling it at time 2. - Move from floor 5 to floor 1 (
requests[1][1]) in 4 seconds, fulfilling it at time 6. - Move from floor 1 to floor 3 (
requests[2][1]) in 2 seconds, reaching at time 8. Its request arrived atrequests[2][0] = 6, so floor 3 is fulfilled at time 8.
Thus, all requests are fulfilled by time 8.
Constraints:
1 <= n <= 1091 <= requests.length <= 16requests[i] == [arrivali, floori]0 <= arrivali <= 1090 <= start, floori <= n - 1
Approach Overview
Problem Overview: You have an elevator with k buttons and a list of n requests, each specifying a target floor. You must decide which requests to serve to maximize the number served, given that the elevator can only stop at floors corresponding to pressed buttons. This is a classic optimization problem where you need to select a subset of requests that can be served in a single trip.
Approach 1: Brute Force (Exponential) (O(2^n * n) time, O(n) space)
Enumerate every subset of requests, check if the floors in that subset can be covered by the k buttons, and track the maximum size. This is straightforward but impractical for n > 20. It shows you understand the combinatorial nature but fails on constraints. Use only to verify correctness on tiny inputs.
Approach 2: Greedy by Floor Frequency (O(n log n) time, O(n) space)
Sort requests by floor, then pick the k most frequent floors. This is a heuristic that works when requests are uniformly distributed, but it fails when requests are clustered or when serving a less frequent floor enables serving many others. It's a good starting point but not optimal.
Approach 3: State Compression DP (Optimal) (O(n * 2^k) time, O(2^k) space)
Use a bitmask to represent which of the k buttons are pressed. For each request, decide whether to serve it based on whether its floor is in the current mask. The key insight is to precompute for each mask the set of floors that can be served, then use DP to find the maximum requests covered. This is the optimal approach because it directly models the decision space without redundant computation. It's the expected solution for interviews.
Recommended for interviews: The state compression DP is what interviewers expect. It demonstrates your ability to model combinatorial problems with bitmasks and optimize with DP. The brute force shows you understand the problem, but the DP shows you can scale. Mention that the greedy is a good heuristic but not correct.
For more on DP and bitmask techniques, check our Bitmask DP and Dynamic Programming guides.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force | O(2^n * n) | O(n) | Only for n <= 20 or verification |
| Greedy | O(n log n) | O(n) | When requests are uniform, quick heuristic |
| State Compression DP | O(n * 2^k) | O(2^k) | General case, optimal solution |