Elevator Requests III solution and explanation
The problem
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.
Solution
The number of floors n can be as large as 10^9, but there are at most m \le 16 requests, so we only need to plan a path among at most m target floors.
This is a traveling salesman problem with arrival-time constraints. Let f[i][j] be the minimum time to fulfill the set of requests represented by bitmask i, with request j fulfilled last.
For each state i that contains request j, let i_0 = i \oplus 2^j:
- If
i_0 = 0, we start fromstart, and the time ismax(|start - floor_j|, arrival_j); - Otherwise, we enumerate the previous request
j_0, and the time ismax(f[i_0][j_0] + |floor_{j_0} - floor_j|, arrival_j).
The answer is the minimum of f[2^m-1][j] over all j.
The time complexity is O(m^2 times 2^m), and the space complexity is O(m times 2^m), where m is the number of requests.
class Solution:
def elevatorRequests(self, n: int, start: int, requests: list[list[int]]) -> int:
m = len(requests)
f = [[0] * m for _ in range(1 << m)]
for i in range(1 << m):
for j in range(m):
if i >> j & 1:
f[i][j] = inf
i0 = i ^ (1 << j)
if i0 == 0:
d = abs(start - requests[j][1])
f[i][j] = min(f[i][j], max(d, requests[j][0]))
else:
for j0 in range(m):
if j0 != j and (i >> j0 & 1):
d = abs(requests[j0][1] - requests[j][1])
f[i][j] = min(
f[i][j], max(f[i0][j0] + d, requests[j][0])
)
return min(f[(1 << m) - 1][j] for j in range(m))class Solution {
public long elevatorRequests(int n, int start, int[][] requests) {
int m = requests.length;
long[][] f = new long[1 << m][m];
for (int i = 0; i < (1 << m); i++) {
for (int j = 0; j < m; j++) {
if (((i >> j) & 1) == 1) {
f[i][j] = Long.MAX_VALUE;
int i0 = i ^ (1 << j);
if (i0 == 0) {
long d = Math.abs(start - requests[j][1]);
f[i][j] = Math.min(f[i][j], Math.max(d, requests[j][0]));
} else {
for (int j0 = 0; j0 < m; j0++) {
if (j0 != j && ((i >> j0) & 1) == 1) {
long d = Math.abs(requests[j0][1] - requests[j][1]);
f[i][j]
= Math.min(f[i][j], Math.max(f[i0][j0] + d, requests[j][0]));
}
}
}
}
}
}
long ans = Long.MAX_VALUE;
for (int j = 0; j < m; j++) {
ans = Math.min(ans, f[(1 << m) - 1][j]);
}
return ans;
}
}class Solution {
public:
long long elevatorRequests(int n, int start, vector<vector<int>>& requests) {
int m = requests.size();
vector<vector<long long>> f(1 << m, vector<long long>(m, 0));
for (int i = 0; i < (1 << m); i++) {
for (int j = 0; j < m; j++) {
if ((i >> j) & 1) {
f[i][j] = LLONG_MAX;
int i0 = i ^ (1 << j);
if (i0 == 0) {
long long d = abs(start - requests[j][1]);
f[i][j] = min(
f[i][j],
max(d, (long long) requests[j][0]));
} else {
for (int j0 = 0; j0 < m; j0++) {
if (j0 != j && ((i >> j0) & 1)) {
long long d = abs(
requests[j0][1] - requests[j][1]);
f[i][j] = min(
f[i][j],
max(
f[i0][j0] + d,
(long long) requests[j][0]));
}
}
}
}
}
}
long long ans = LLONG_MAX;
for (int j = 0; j < m; j++) {
ans = min(ans, f[(1 << m) - 1][j]);
}
return ans;
}
};function elevatorRequests(n: number, start: number, requests: number[][]): number {
const m = requests.length;
const f: number[][] = Array.from({ length: 1 << m }, () => Array(m).fill(0));
for (let i = 0; i < 1 << m; i++) {
for (let j = 0; j < m; j++) {
if (((i >> j) & 1) === 1) {
f[i][j] = Infinity;
const i0 = i ^ (1 << j);
if (i0 === 0) {
const d = Math.abs(start - requests[j][1]);
f[i][j] = Math.min(f[i][j], Math.max(d, requests[j][0]));
} else {
for (let j0 = 0; j0 < m; j0++) {
if (j0 !== j && ((i >> j0) & 1) === 1) {
const d = Math.abs(requests[j0][1] - requests[j][1]);
f[i][j] = Math.min(f[i][j], Math.max(f[i0][j0] + d, requests[j][0]));
}
}
}
}
}
}
const full = (1 << m) - 1;
let ans = Infinity;
for (let j = 0; j < m; j++) {
ans = Math.min(ans, f[full][j]);
}
return ans;
}func elevatorRequests(n int, start int, requests [][]int) int64 {
m := len(requests)
f := make([][]int64, 1<<m)
for i := range f {
f[i] = make([]int64, m)
}
const INF int64 = 1 << 60
for i := 0; i < 1<<m; i++ {
for j := 0; j < m; j++ {
if (i>>j)&1 == 1 {
f[i][j] = INF
i0 := i ^ (1 << j)
if i0 == 0 {
d := int64(abs(start - requests[j][1]))
f[i][j] = min(
f[i][j],
max(d, int64(requests[j][0])),
)
} else {
for j0 := 0; j0 < m; j0++ {
if j0 != j && (i>>j0)&1 == 1 {
d := int64(abs(
requests[j0][1] - requests[j][1],
))
f[i][j] = min(
f[i][j],
max(
f[i0][j0]+d,
int64(requests[j][0]),
),
)
}
}
}
}
}
}
full := (1 << m) - 1
ans := INF
for j := 0; j < m; j++ {
ans = min(ans, f[full][j])
}
return ans
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}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 |
Frequently asked questions
Elevator Requests III Python solution?
In Python, you can implement state compression DP using a list of size 2^k for DP and precompute a list of sets for each mask. The code is concise and runs in O(n * 2^k) time.
Is Elevator Requests III easy or hard?
It is rated Hard. The challenge lies in recognizing the bitmask DP pattern and efficiently computing the maximum requests, which requires careful state design.
How to solve Elevator Requests III in O(n * 2^k)?
Use bitmask DP: precompute for each mask the set of floors that can be served, then iterate through requests and update DP[mask] = max(DP[mask], DP[mask without button] + count). This achieves O(n * 2^k) time.
What is the best approach for Elevator Requests III?
The best approach is state compression DP, which uses bitmask to represent button selections and computes the maximum requests served in O(n * 2^k) time and O(2^k) space. It is optimal for the problem's constraints.
Is Elevator Requests III asked at Google/Amazon/Meta?
Yes, this problem is typical of hard DP questions asked at top tech companies like Google, Amazon, and Meta, testing your ability to optimize combinatorial decisions.
What data structure is used in Elevator Requests III?
The optimal solution uses a bitmask (integer) to represent the state of pressed buttons and a DP array indexed by mask. This compact representation is key to efficiency.
What is the time complexity of Elevator Requests III?
The optimal state compression DP solution runs in O(n * 2^k) time, where n is the number of requests and k is the number of buttons. Space complexity is O(2^k) for the DP table.