1066. Campus Bikes II

On a campus represented as a 2D grid, there are Nworkers and Mbikes, with N <= M. Each worker and bike is a 2D coordinate on this grid.

We assign one unique bike to each worker so that the sum of the Manhattan distances between each worker and their assigned bike is minimized.

The Manhattan distance between two points p1and p2is Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.

Return the minimum possible sum of Manhattan distances between each worker and their assigned bike.

Example 1:

Input: 
workers = [[0,0],[2,1]], 
bikes = [[1,2],[3,3]]
Output: 6
Explanation: 

We assign bike 0 to worker 0, bike 1 to worker 1. The Manhattan distance of both assignments is 3, so the output is 6.

Example 2:

Input: 
workers = [[0,0],[1,1],[2,0]], 
bikes = [[1,0],[2,2],[2,1]]
Output: 4
Explanation: 

We first assign bike 0 to worker 0, then assign bike 1 to worker 1 or worker 2, bike 2 to worker 2 or worker 1. Both assignments lead to sum of the Manhattan distances as 4.

Note:

1. 0 <= workers[i][0], workers[i][1], bikes[i][0], bikes[i][1] < 1000

2. All worker and bike locations are distinct.

3. 1 <= workers.length <= bikes.length <= 10

Thoughts:

1. Dijkstra on augmented path: vertex: states of chosen bikes, edge: Manhattan distance between worker i and bike j (Original Post)

2. Minimum-cost flow (Original Post): 1. Construct the graph by attaching the source and sink node along with workers and bikes node (vertex). 2. Construct the edge of the graph with capacity and cost connecting two nodes (vertices). 3. Iteratively sending flow 1 to the graph: 1. Using Bellman-ford to find the shortest path between on source and sink on current graph connection 2. Update the graph connection by augmenting path update as subtracting 1 (flow) from forward edges and add 1 for reverse edges for each node. 3. Adding the current flow cost to the answer. 4. Finally return the answer

3. DFS with early pruning (Original Post)

4. DFS with memorization (Original Post)

5. bitmasking DP (Original Post)

Code: Dijkstra on augmented path:

class Solution(object):
    def assignBikes(self, workers, bikes):
        """
        :type workers: List[List[int]]
        :type bikes: List[List[int]]
        :rtype: int
        """
        def dis(i, j):
            return abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1])
        h = [[0, 0, 0]]
        seen = set()
        while True:
            cost, i, taken = heapq.heappop(h)
            # Filter out cases (path sum) in which bikes have been assigned 
            if taken in seen: continue
            seen.add(taken)
            if i == len(workers):
                return cost
            for j in xrange(len(bikes)):
                if taken & (1 << j) == 0:
                    heapq.heappush(h, [cost + dis(i,j), i + 1 , taken | (1 << j)])

Code: Minumum-cost flow: (Fav) T:((m * n) * m) : [O(|E|f)]

class Solution:
    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:
        m, n = len(workers), len(bikes)
        # 0 ~ m - 1 workers
        # m ~ m + n - 1 bikes
        s = m + n
        t = m + n + 1
        num_nodes = m + n + 2

        g = [[] for _ in range(num_nodes)]
        prevv = [None] * num_nodes # prevv[v]: the prev node of node v 
        preve = [None] * num_nodes # preve[v]: the edge that connects to v: (prevv[v], v)

        def add_edge(from_node, to_node, cap, cost):
            g[from_node] += [[to_node, cap, cost, len(g[to_node])]]  # ID for to_node's reverse edge from from_node, accessed by g[v][g[g[prevv[v]][preve[v]][3]]

            g[to_node] += [[from_node, 0, -cost, len(g[from_node]) - 1]] # ID for reverse edge

        # Find minimum cost to flow f from s to t 
        def min_cost_flow(s,t,f):
            ans = 0
            # Bellman-ford to expand the path 
            while f > 0:
                # Iteratively send flow 1 to the new graph
                dist = [float('inf')] * (m + n + 2)
                dist[s] = 0
                update = True

                while update:
                    update = False
                    for v in range(num_nodes):
                        if dist[v] == float('inf'):
                            continue
                        # relax on v
                        for i, edge in enumerate(g[v]):
                            to_node, cap, cost, reverse_id = edge
                            if cap > 0 and dist[to_node] > dist[v] + cost:
                                dist[to_node] = dist[v] + cost
                                prevv[to_node] = v
                                preve[to_node] = i
                                update = True # Re-sending the flow 
                # update flow by decreasing the capacity of edges along the flow path
                d = f 
                v = t
                # Generic coding of flow algo
                # First pass to determine the bottleneck of the flow 
                while v!= s:
                    d = min(d, g[prevv[v]][preve[v]][1])# d = 1 for this problem
                    v = prevv[v] 
                f -= d
                ans += d * dist[t]# d = 1 for this problem, so actaully ans += dist[t]

                # Second pass to update the capacity of the edges along the flow path
                v = t 
                while v != s: 
                    edge = g[prevv[v]][preve[v]]
                    # forward 
                    edge[1] -=d 
                    # residual
                    g[v][edge[3]][1] += d 
                    v = prevv[v]

            return ans 

        # Adding edges

        # Source to workers: cap = 1, cost = 0
        for i in range(m):
            add_edge(s, i, 1, 0)

        # Workers to bikes
        for i in range(m):
            for j in range(n):
                x1, y1 = workers[i]
                x2, y2 = bikes[j]
                c = abs(x1 - x2) + abs(y1 - y2)
                add_edge(i, j + m, 1, c)

        # Bikes to sink
        for j in range(n):
            add_edge(j + m, t, 1, 0)

        return min_cost_flow(s, t, m)

Code: DFS with early pruning:

class Solution {
    int min = Integer.MAX_VALUE;
    public int assignBikes(int[][] workers, int[][] bikes) {
        dfs(new boolean[bikes.length], workers, 0, bikes, 0);
        return min;
    }

    public void dfs(boolean[] visited, int[][] workers, int i, int[][]bikes, int dist){
        if (i >= workers.length){
            min = Math.min(dist, min);
            return;
        }

        // Early pruning 
        if (dist > min){
            return;
        }

        for(int j = 0; j < bikes.length; j++){
            if(visited[j]) continue;
            visited[j] = true;
            dfs(visited, workers, i + 1, bikes, dist + dis(bikes[j] , workers[i]));
            visited[j] = false;
        }
    }

    public int dis(int[] p1, int [] p2){
        return Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]);
    }
}