Mira rides at a snow park. Every morning she either rents a board for that day or buys
one, after which she never pays again. Prices change during the season: on her i-th riding day
the rental costs rent[i] and a new board costs buy[i]. She does not know how many riding days
the season will give her (the lists cover the riding days the season turned out to have), so she follows this
rule each morning:
- if she has not bought yet and
paid + rent[i] >= buy[i], wherepaidis the rent she has paid so far, she buys today; - otherwise she rents.
With hindsight she could have spent less. Return a tuple (rule_cost, best_cost): what the rule
cost her in total, and the cheapest possible total for the same days if she had known all the
prices in advance.
Examples
Input: rent = [4, 4, 4, 4, 4, 4, 4, 4], buy = [20, 20, 20, 20, 20, 20, 20, 20]
Output: (36, 20)
Explanation: she rents on days 0-3 (16 paid); on day 4, 16 + 4 >= 20, so she buys: 36.
Buying on day 0 would have cost 20.
Input: rent = [5, 5], buy = [12, 12]
Output: (10, 10)
Explanation: the season ends before buying pays off, and renting both days is the best choice.
Input: rent = [3, 3, 3], buy = [50, 7, 50]
Output: (9, 9)
Explanation: on day 1, 3 + 3 < 7, so she rents; renting all three days costs 9, which is
also the best choice (renting once and buying on day 1 costs 10).
Constraints
0 <= len(rent) == len(buy) <= 10**51 <= rent[i], buy[i] <= 10**6- Target: O(n) time
Goals
- Simulate a rule that decides each day without knowing how many days follow
- Compute the best decision with hindsight in one pass
- Compare an online cost with the offline optimum