Lift-to-stairs switch with an energy budget

You start on floor 0 of a building with 0 energy and need to reach floor n. You ride the lift from floor 0 up to some floor k (0 <= k <= n), then walk the stairs from floor k to floor n.

• Lift: each floor adds e1 energy and takes t1 time. Lift time is k * t1.
• Stairs: a floor climbed while your current energy is E takes ceil(c / E) time, and then your energy drops by e2. Stair time is the sum over the n - k stair floors.
• Your energy may never drop below 0. A switch floor k is valid only if you finish the stairs with energy >= 0, that is k * e1 - (n - k) * e2 >= 0.

Implement:

def min_time_difference(n: int, e1: int, t1: int, e2: int, c: int) -> int:
    ...

Return the minimum value of |lift time - stair time| over all valid switch floors k. Riding the lift all the way (k = n, no stairs) is always valid.

Constraints: 1 <= n, e1, t1, e2, c <= 10^5. An O(n^2) simulation is too slow for the largest inputs.

Example 1

n = 3, e1 = 2, t1 = 5, e2 = 1, c = 4   ->   1

• k = 0: invalid (no energy).
• k = 1: lift time 5, energy 2. Stairs cost ceil(4/2) = 2 (energy 1), then ceil(4/1) = 4 (energy 0). Stair time 6, difference 1.
• k = 2: lift time 10, energy 4, one stair floor costs 1. Difference 9.
• k = 3: lift time 15, no stairs. Difference 15.

Example 2

n = 4, e1 = 3, t1 = 2, e2 = 2, c = 7   ->   0

Switch at k = 2: lift time 4, energy 6. Stairs cost ceil(7/6) = 2 (energy 4), then ceil(7/4) = 2 (energy 2). Stair time 4, difference 0. k = 1 is invalid: energy 3 cannot cover three stair floors at 2 each.