Problem Link - Posting
Problem Statement
Chef has been promoted to the position of Director of Human Resources for the Siruseri Government!
In Siruseri, there is a long, straight, highway. There are n houses and m offices along the highway. The highway is abstracted as an integer axis, and the position of each house and office as a single integer coordinate. The i^{th} house is at coordinate a_i and the i^{th} office is at coordinate b_i.
Each house has one (1) government employee living in it. Chef needs to assign each employee an office to work in. However, each office has manpower requirements. The i^{th} office can take between s_i and e_i employees. More formally, if the i^{th} office takes k_i employees, then s_i \leq k_i \leq e_i must be satisfied.
We define the commute distance of an employee as the distance between their house and the office they are assigned to work in. Chef asks the following question: what is the minimum possible sum of commute distances across all assignment schemes satisfying the manpower requirements?
Formally, let the office that employee i is assigned to be o_i. Then, you are asked to minimise \sum_{i=1}^{n} |a_i - b_{o_i}|, while satisfying the manpower requirements for each office.
If there are no assignment schemes that satisfy the manpower requirements, report this.
Approach
To solve the problem, the logic is based on using dynamic programming to find the optimal way to assign employees to offices while minimizing total commute distance. First, sort the houses and offices by their positions so that it’s easier to calculate distances. For each office, we need to decide how many employees to assign, but within the limits given by the constraints (s_i and e_i for each office).
The idea is to maintain a DP array that tracks the minimum cost of assigning employees up to each point. For every office, we calculate the cost of assigning each house to that office. The challenge is ensuring that the number of employees falls within the required range for each office. This is done using a sliding window technique with a deque to efficiently manage and update possible assignments as you iterate through the houses. At the end of the process, if a feasible assignment exists, return the minimum cost; otherwise, return -1 to indicate no valid assignment is possible.
Time complexity
The time complexity is approximately O(n \times m), where n is the number of houses and m is the number of offices.
Space complexity
The space complexity is O(n \times m) due to the DP table and cost calculations.