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, representing the floor where the elevator begins, and an integer array requests, where requests[i] is a floor that the elevator is requested to reach. All floors in requests are distinct.
At time 0, the elevator is on floor start, and all requests are made simultaneously.
During each second before all requests are fulfilled, the elevator moves exactly one floor, either up or down. A request is fulfilled instantly when the elevator reaches its requested floor. If start appears in requests, that request is fulfilled at time 0.
For each second that a request remains unfulfilled, you receive 1 penalty. Equivalently, a request fulfilled at time t contributes t to the total penalty.
Return the minimum total penalty required to fulfill all requests.
Example 1:
Input: n = 6, start = 4, requests = [1,5]
Output: 6
Explanation:
start) to floor 5 in 1 second. Penalty for floor 5 is 1.Thus, the total penalty is 1 + 5 = 6.
Example 2:
Input: n = 8, start = 3, requests = [3,7,1]
Output: 10
Explanation:
start) is fulfilled instantly. Penalty for floor 3 is 0.Thus, the total penalty is 0 + 2 + 8 = 10.
Example 3:
Input: n = 10, start = 5, requests = [0,2,9]
Output: 22
Explanation:
start) to floor 2 in 3 seconds. Penalty for floor 2 is 3.Thus, the total penalty is 3 + 5 + 14 = 22.
Constraints:
1 <= n <= 1091 <= requests.length <= 15000 <= start, requests[i] <= n - 1requests are distinct.Sort the requested floors. If start is itself requested, its request contributes 0 and can be considered already fulfilled.
Once the elevator has visited a leftmost and rightmost floor, every requested floor between them has also been fulfilled. Therefore, use interval DP and keep track of whether the elevator is currently at the left or right endpoint of the visited interval.
When the elevator moves a distance d while k requests are still unfulfilled, the total penalty increases by k * d.
Insert start into the sorted positions and begin with an interval containing only start. From a state [l, r], expand to the next requested floor on either the left or the right, updating the cost according to the current endpoint and the number of requests still unfulfilled.
There are O(m^2) intervals, where m = requests.length, and two possible endpoint states for each interval. Use 64-bit integers for the penalty.
6 4 [1,5]
8 3 [3,7,1]
10 5 [0,2,9]