Orbital Relay Coverage Budget
Minimum total cost of intervals covering zero to each target without gaps
A spacecraft must maintain an uninterrupted relay connection from mission time 0 through a requested target time. Each available relay contract is described by [start, end, cost]. Purchasing that contract provides connection throughout the closed time interval [start, end] and charges cost once.
You may purchase any subset of contracts. Their combined coverage must contain every real-valued time in [0, target]; a gap of any positive length is not allowed. Contracts that meet at an endpoint provide uninterrupted coverage. Coverage beyond the target is allowed.
For each time in targets, return the minimum total cost of contracts that provide uninterrupted coverage from 0 through that time. Return -1 if this is impossible. Reaching time 0 requires no contract and costs 0.
Each target is an independent planning question: contracts purchased for one target are not carried over to another. Return answers in the original order of targets.
Examples
Example 1
Input: contracts = [[0,4,3],[4,9,5],[0,9,12]], targets = [0,3,9,10] Output: [0,3,8,-1]
The first contract covers the initial part of the mission, and the second meets it at time 4. Together they are cheaper than buying the long contract. The last target lies beyond every contract's coverage.
Example 2
Input: contracts = [[3,7,4],[8,12,1],[0,4,2]], targets = [4,6,8,12] Output: [2,6,-1,-1]
The first two contracts overlap and can provide continuous coverage through time 7. The final contract starts at time 8, leaving a positive-length gap that prevents reaching later targets.
Example 3
Input: contracts = [[0,5,9],[0,5,2],[5,8,3]], targets = [8,0,5,8] Output: [5,0,2,5]
The duplicate coverage windows have different prices, so only the cheaper one is useful. Targets may be repeated or supplied out of chronological order.
Constraints
- 0 <= contracts.length <= 4000
- Each contract has exactly three integers: [start, end, cost].
- 0 <= start < end <= 10^9
- 1 <= cost <= 10^9
- 1 <= targets.length <= 1000
- 0 <= targets[i] <= 10^9
- Contracts and targets may be unsorted and may contain duplicates.
The intended solution runs in O(n log n + q log q) time and O(n + q) space, where n is the number of contracts and q is the number of targets. All costs and answers fit exactly in JavaScript's integer-safe number range.
Hints
Show hint 1Hint 1
When a contract starts at time s, consider the cheapest already-constructed plan whose coverage reaches at least s. Adding this contract creates another possible coverage frontier.
Show hint 2Hint 2
Sweep starts and targets chronologically. Store frontier candidates by total cost in a heap, and lazily discard candidates whose coverage ends before the current time.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you reconstruct one minimum-cost set of contract indices for a single target?
- How would the sweep change if a fixed initial interval [0, initialEnd] were already covered for free?
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