Assign Distinct Chargers to Vehicles with Minimum Total Distance

On a one-dimensional line, vehicles and chargers have integer positions. Assign every vehicle to a distinct charger so that the sum of absolute driving distances is minimized. Some chargers may remain unused. If there are fewer chargers than vehicles, the assignment is impossible. Given a target vehicle index, return the charger assigned to that vehicle in a globally optimal assignment. ### Input and Output For this practice formulation, vehicle and charger indices identify entries in separate position lists; preserve these identities when sorting by position. The target index must identify a vehicle. Duplicate positions, if supplied, still represent distinct indexed entities. Report impossibility separately from a charger index. The source does not specify a tie rule for multiple globally optimal assignments. Any target charger that belongs to some complete globally optimal assignment is acceptable; do not silently require a lexicographically preferred assignment. For a vehicle at position `1` and chargers at `0` and `2`, either charger is valid. ### Constraints and Clarifications The sorted dynamic-programming follow-up is specifically one-dimensional. Do not assume that its noncrossing argument solves arbitrary two-dimensional assignment. No numerical input-size bounds were reported. Individual nearest choices may reuse a charger and are not a feasible assignment in general. ### What a Strong Answer Covers Prove that a noncrossing optimum exists, derive a dynamic program that can skip chargers, reconstruct an assignment, and retrieve the target vehicle's result. Explain why greedily taking the currently shortest available pair can lose global optimality. ### Follow-up Questions How much memory is needed if only the minimum cost is requested? What if the interviewer requires one particular tie rule? What changes for positions on a two-dimensional grid?