Minimum cost to repair road

Question

Let us assume there is highway

There are N potholes at points [p1, p2, p3...., pn]

There are equal number of service crew at points [s1, s2, s3...., sn]

One service crew can repair one pothole only

The cost to send a crew at point pX to repair a pothole at point sX is |pX-sX|

How would you find the minimum cost to repair the road?

Ex:

Potholes are at [3, 5, 7]

Service Crew are stationed at [1, 3, 5]

Few possible combinations are:

1->3, 3->5, 5->7 (Cost = 6)

1->5, 3->7, 5->3 (Cost = 10)

Share/Explain the algorithm you'd use to solve this problem?

What is the time & space complexity of your algorithm?

Answer 1

In this example it should be 6, no matter what!

This is the problem of finding maximum matching in a fully connected bipartite graph.

If the problem has same number of potholes and crews, it's a perfect matching.

• Intention would be to find out maximum matching between potholes P and crews C.
• Assumption: A pothole can be serviced by any crew.
• Matching condition: |P(i) - C(j)| is minimum.