Box Office Paired Seat Reserve
Minimum total gap for k disjoint adjacent pairs in an increasing array
A theater has a row of movable seats positioned along a rail. The box office wants to reserve exactly k two-seat bundles for an upcoming performance.
The strictly increasing array positions gives the rail coordinate of each available seat. A permitted bundle consists of seats at consecutive indices i and i + 1 in this array. Its spacing cost is positions[i + 1] - positions[i].
No seat may belong to more than one reserved bundle. Seats that are not reserved may remain unused.
Return the minimum possible total spacing cost of exactly k permitted bundles. When k is zero, return 0.
Examples
Example 1
Input: positions = [0,4,5,9], k = 2 Output: 8
The middle bundle has the smallest individual cost, but reserving it prevents reserving either neighboring bundle. Since two bundles are required, the first two seats and the last two seats must be paired.
Example 2
Input: positions = [0,1,8,13,14,30], k = 2 Output: 2
Reserve the seats at coordinates 0 and 1 together, and the seats at coordinates 13 and 14 together. The other available seats can remain unused.
Example 3
Input: positions = [-7,2,12], k = 0 Output: 0
No bundles are requested, so no seats need to be reserved.
Constraints
- 0 <= positions.length <= 6000
- -1000000 <= positions[i] <= 1000000
- positions is strictly increasing.
- 0 <= k <= floor(positions.length / 2)
The intended solution runs in O(n log n) time and O(n) space. Contraction is not ordinary greedy deletion: the replacement edge represents exchanging the selected edge for both of its neighbors. Infinite-cost boundary edges prevent impossible exchanges. Equal costs require no output tie-break because only the minimum total cost is returned.
Hints
Show hint 1Hint 1
View every permitted bundle as an edge between neighboring seats. What can an optimal selection do around the cheapest remaining edge?
Show hint 2Hint 2
After taking the cheapest edge, preserve the alternative of taking both neighboring edges by replacing its cost with left_cost + right_cost - chosen_cost. Use a heap for costs and linked neighbors for contractions.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you reconstruct one minimum-cost collection of bundles instead of returning only its cost?
- Why does repeatedly choosing the cheapest bundle and permanently discarding its neighbors fail, even though the contraction method succeeds?
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