Welcome to Subscribe On Youtube
4027. Elevator Requests III
Description
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
Solutions
Solution 1: State Compression DP
Thinking
Floor indices reach $10^9$, but there are only $m\le 16$ requests, which is exactly the size of a subset TSP. Arrival times are lower bounds: arriving early forces a wait.
$f[S][j]$ is the earliest time to have processed set $S$ and ended on request $j$. From the empty set the cost is $\max(|\textit{start}-\textit{floor}_j|,\textit{arrival}_j)$; otherwise we enumerate the previous request $j_0$ and take $\max(f[S\setminus{j}][j_0]+\text{distance},\textit{arrival}_j)$.
The minimum over the last index on the full set is the time to finish every request.
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 from $\textit{start}$, and the time is $\max(|\textit{start} - \textit{floor}_j|, \textit{arrival}_j)$;
- Otherwise, we enumerate the previous request $j_0$, and the time is $\max(f[i_0][j_0] + |\textit{floor}_{j_0} - \textit{floor}_j|, \textit{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 { 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; } }; -
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)) -
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 } -
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; }