Leetcode: 2477. Minimum Fuel Cost to Report to the Capital

Problem Statement

Patterns

Prompts

Solution

Let's start with a definition for leaf and parent cities. A leaf city is a city with only one connection to an other city which we call parent city. By this definition, the representative in a leaf city has only one option to go to the capital which is driving first to their parent cities.

The solution consists on executing the following reduction to the input tree. We move representatives from leaf cities to their parent cities. Then, we remove the leaf cities from the tree what creates new leaf cities since some parent cities will have only one connection remaining. If there is only one city left, it must be the capital and the problem is solved. Otherwise, we execute the same process again. While we move the representatives, we keep track of the accumulated cost so far and the number of representatives waiting to drive to the capital. Since we can take an local optimal decision to move representatives from leaf to parent cities, this is a Greedy algorithm. And you can implement it using a Depth-first search with time and space complexity of \(O(n)\). 

class Solution:
    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
        N = len(roads) + 1
        A = [[] for _ in range(N)]
        for u, v in roads:
            A[u].append(v)
            A[v].append(u)

        def dfs(u, p):
            total, count = 0, 1
            for v in A[u]:
                if v != p:
                    ecost, ecount = dfs(v, u)
                    total += ecost
                    count += ecount
            if u == 0:
                return total
            return total + ceil(count / seats), count

        return dfs(0, None)

Cited by 1