Skip to content

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. 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 <= 109
  • 1 <= requests.length <= 16
  • requests[i] == [arrivali, floori]
  • 0 <= arrivali <= 109
  • 0 <= start, floori <= n - 1

Solutions

Solution 1: State Compression DP

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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;
}

Comments