Bus Log Replay Plans
Minimum cost and count of optimal ways to consume two arrays in order
A city transit control room is replaying the arrival logs of two buses. Each log lists arrival timestamps in nondecreasing order. Every record must be replayed, and records from the same bus must retain their original order.
A replay plan consists of a sequence of the following actions:
- A: consume the next record from
first, payingsoloFee. - B: consume the next record from
second, payingsoloFee. - P: consume the next record from each log together, paying the absolute difference between their timestamps.
An action is allowed only when all records it consumes are still available. The replay ends when both logs have been completely consumed. Its total cost is the sum of its action costs.
Return a two-element array [minimumCost, optimalPlanCount], where optimalPlanCount is the number of minimum-cost replay plans, modulo 1,000,000,007.
Plans are distinguished by their action strings. In particular, AB and BA are different plans, even when the consumed timestamps are equal. Records with equal timestamps remain separate records. If both logs are empty, there is exactly one plan: the empty action string.
Examples
Example 1
Input: first = [4,10], second = [5,11], soloFee = 3 Output: [2,1]
Pairing both corresponding records costs one unit per pair. This is cheaper than replacing either pair with two solo actions, so the unique optimal action string is PP.
Example 2
Input: first = [2], second = [8], soloFee = 3 Output: [6,3]
The paired action costs exactly as much as two solo actions. P, AB, and BA therefore all attain the minimum cost.
Example 3
Input: first = [], second = [0,5,5], soloFee = 2 Output: [6,1]
The first log is empty, so every record in the second log must be consumed with a B action. There is only one possible action string.
Constraints
- 0 <= first.length, second.length <= 1000
- 0 <= first[i], second[j] <= 1,000,000
- Both timestamp arrays are in nondecreasing order.
- 0 <= soloFee <= 1,000,000
The intended solution takes O(first.length * second.length + first.length + second.length) time and O(second.length + 1) auxiliary space. Counting action strings, rather than only sets of paired records, makes the predecessor cases disjoint.
Hints
Show hint 1Hint 1
Use a state describing how many records have been consumed from each log. Which states can immediately precede it?
Show hint 2Hint 2
Store both the best cost and its number of plans. Replace the count when a cheaper transition is found, and add counts when transition costs tie.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you also return the lexicographically smallest optimal action string under A < B < P?
- How would the recurrence change if a paired action were allowed only when its timestamp difference was at most a given tolerance?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem