Elevator Requests III - Solution & Explanation

Hard8 min read

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] = [arrival_i, floor_i] indicates that a request for floor_i is made at time arrival_i.

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. Since requests[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. Since requests[0][0] = 1 has 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. Since requests[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 at requests[2][0] = 6, so floor 3 is fulfilled at time 8.

Thus, all requests are fulfilled by time 8.

Constraints:

1 <= n <= 10⁹
1 <= requests.length <= 16
requests[i] == [arrival_i, floor_i]
0 <= arrival_i <= 10⁹
0 <= start, floor_i <= n - 1

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 from start, and the time is max(|start - floor_j|, arrival_j);
Otherwise, we enumerate the previous request j_0, and the time is max(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.