Weather Archive Gap Fees
Minimum cost to pair or discard elements of two ordered arrays
A weather station is reconciling two ordered archives of temperature readings, first and second. Readings must be processed in their original order, but the archives do not have to contain the same number of readings.
Starting with both archives unprocessed, repeatedly perform one of these actions:
- Pair: consume the next reading from each archive. The cost is the absolute difference between the two readings.
- Discard from first: consume only the next reading from
first. - Discard from second: consume only the next reading from
second.
Every discard costs per_reading. In addition, the first discard in each consecutive run of discards from the same archive costs startup. A pair action or a discard from the other archive ends that run. Thus, discarding three readings from first consecutively costs startup + 3 * per_reading.
An action is allowed only when all readings it consumes are still available. All readings in both archives must eventually be consumed. Pairing is optional, and either archive may be empty.
Return the minimum total reconciliation cost.
Examples
Example 1
Input: first = [10,50,60,20], second = [10,20], startup = 5, per_reading = 2 Output: 9
Pair the two readings of value 10, discard the consecutive readings 50 and 60 from the first archive as one run, and pair the two readings of value 20. The discard run pays its startup fee only once.
Example 2
Input: first = [], second = [-3,0,4], startup = 7, per_reading = 1 Output: 10
The first archive is empty, so all readings in the second archive must be discarded. They can be processed in a single consecutive run.
Example 3
Input: first = [0,100,0], second = [0,-100,0], startup = 3, per_reading = 2 Output: 10
Pairing every reading is not necessarily cheapest: the middle readings differ sharply, so discarding them from their respective archives can be preferable. Switching archives starts a new discard run.
Constraints
- 0 <= first.length, second.length <= 600
- -1000 <= first[i], second[i] <= 1000
- 0 <= startup <= 1000
- 0 <= per_reading <= 1000
- All inputs are integers.
The intended solution takes O(first.length * second.length + first.length + second.length) time and O(second.length + 1) auxiliary space. Discard runs are defined by consecutive actions, not merely by consecutive indices within an archive.
Hints
Show hint 1Hint 1
Use the numbers of consumed readings from the two archives as your two dynamic-programming coordinates.
Show hint 2Hint 2
At each coordinate, distinguish whether the last action was a pair, a discard from first, or a discard from second. This determines whether the next discard needs a startup fee.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you reconstruct one minimum-cost action sequence, breaking ties by a specified ordering of the three action types?
- How would the recurrence change if each archive had its own startup fee and per-reading discard fee?
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