LeetCode 2285 - Maximum Total Importance of Roads

LeetCode Problem 2285

Difficulty: 🟡 Medium
Topics: Greedy, Graph Theory, Sorting, Heap (Priority Queue)

Solution

Here is the complete technical solution guide for LeetCode 2285 following your requested format and level of detail:

Problem Understanding

The problem gives you n cities, numbered from 0 to n - 1, and a list of bidirectional roads connecting pairs of cities. Each city must be assigned a unique integer value from 1 to n, and the importance of a road is defined as the sum of the values of its two connected cities. The goal is to assign values in a way that maximizes the total importance of all roads.

Inputs are:

• n: the number of cities, ranging from 2 up to 50,000.
• roads: a list of pairs [a, b] representing bidirectional connections. Each road is unique.

The output is a single integer, the maximum total importance of all roads.

Key observations include that cities connected to more roads should receive higher values to maximize the sum contributions. This is because each road’s contribution is the sum of its two cities’ values; assigning higher numbers to more connected cities contributes more times to the total.

Important edge cases include:

• Cities with no connections: their assigned value does not affect total importance.
• Sparse road networks where some cities have only one road.
• Dense road networks where some cities have multiple connections.

The problem guarantees there are no duplicate roads and ai != bi, so we do not need to check for invalid input.

Approaches

Brute Force

A brute-force solution would try every permutation of numbers 1 to n assigned to the cities. For each permutation, compute the sum of road importances by summing value[a] + value[b] for each road [a,b]. Return the maximum sum found.

This approach is correct but computationally infeasible because there are n! permutations. Even for n = 10, 10! = 3,628,800, and for n = 50,000 it is impossible.

Optimal Greedy Approach

The key insight is that a city with more roads contributes more to the total importance, since each road’s importance depends on its two endpoints. Therefore:

1. Count the number of roads connected to each city (the degree).
2. Assign the highest numbers to the cities with the highest degrees.
3. Sum the importance using these assignments.

This approach guarantees that every unit increase in a city’s assigned value is applied to as many roads as possible, maximizing total importance. Sorting cities by degree allows us to assign values optimally.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n! * m)	O(n)	Check every permutation of city values
Optimal Greedy	O(n + m + n log n)	O(n)	Sort cities by degree, assign values, sum contributions

Here, n is the number of cities, and m is the number of roads.

Algorithm Walkthrough

1. Initialize an array degree of size n to count the number of roads connected to each city.
2. Iterate through roads, and for each road [a, b], increment degree[a] and degree[b]. This computes each city’s connectivity.
3. Create a list of tuples (city_index, degree[city_index]).
4. Sort this list in descending order by degree. Cities with more connections will appear first.
5. Assign values from n down to 1 according to this sorted order. The most connected city gets n, the next gets n-1, and so on.
6. Iterate through the original roads list, and for each road [a, b], sum assigned_value[a] + assigned_value[b] into total_importance.
7. Return total_importance.

Why it works: Each city contributes its value to every connected road. Assigning higher numbers to cities with higher degrees maximizes the total sum, as each increment in a high-degree city propagates across many roads.

Python Solution

from typing import List

class Solution:
    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:
        degree = [0] * n
        for a, b in roads:
            degree[a] += 1
            degree[b] += 1
        
        # Sort cities by degree in descending order
        city_order = sorted(range(n), key=lambda x: degree[x], reverse=True)
        
        # Assign values from n down to 1
        assigned_value = [0] * n
        for i, city in enumerate(city_order):
            assigned_value[city] = n - i
        
        # Sum importance of all roads
        total_importance = 0
        for a, b in roads:
            total_importance += assigned_value[a] + assigned_value[b]
        
        return total_importance

Explanation:

• First, the degree array counts how many roads each city participates in.
• city_order sorts cities by degree to decide value assignment.
• assigned_value maps each city index to its assigned integer.
• Finally, we iterate over the roads and compute the total importance.

Go Solution

func maximumImportance(n int, roads [][]int) int64 {
    degree := make([]int, n)
    for _, road := range roads {
        degree[road[0]]++
        degree[road[1]]++
    }
    
    type cityDeg struct {
        idx int
        deg int
    }
    
    cities := make([]cityDeg, n)
    for i := 0; i < n; i++ {
        cities[i] = cityDeg{i, degree[i]}
    }
    
    // Sort by degree descending
    sort.Slice(cities, func(i, j int) bool {
        return cities[i].deg > cities[j].deg
    })
    
    assignedValue := make([]int, n)
    for i, city := range cities {
        assignedValue[city.idx] = n - i
    }
    
    var total int64
    for _, road := range roads {
        total += int64(assignedValue[road[0]] + assignedValue[road[1]])
    }
    
    return total
}

Go-specific notes:

• We define a struct cityDeg to pair indices with degrees.
• Sorting uses sort.Slice with a custom comparator.
• Use int64 for total to avoid integer overflow since n can be up to 50,000.

Worked Examples

Example 1

Input: n = 5, roads = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]

1. Compute degrees: [2, 3, 4, 2, 1]
2. Sort cities by degree: [2, 1, 0, 3, 4]
3. Assign values from 5 down to 1: [3, 4, 5, 2, 1]
4. Compute road importance:

Road	Sum
0,1	3 + 4 = 7
1,2	4 + 5 = 9
2,3	5 + 2 = 7
0,2	3 + 5 = 8
1,3	4 + 2 = 6
2,4	5 + 1 = 6

Total = 7 + 9 + 7 + 8 + 6 + 6 = 43

Example 2

Input: n = 5, roads = [[0,3],[2,4],[1,3]]

1. Degrees: [1, 1, 1, 2, 1]
2. Sorted: [3,0,1,2,4]
3. Assign values: [4,3,2,5,1]
4. Road sums:

Road	Sum
0,3	4 + 5 = 9
2,4	2 + 1 = 3
1,3	3 + 5 = 8

Total = 20

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m + n log n)	O(m) for counting degrees, O(n log n) for sorting, O(m) for computing total
Space	O(n)	Arrays degree and assigned_value

The algorithm is efficient enough for n, m <= 5 * 10^4.

Test Cases

# Provided examples
assert Solution().maximumImportance(5, [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]) == 43  # example 1
assert Solution().maximumImportance(5, [[0,3],[2,4],[1,3]]) == 20  # example 2

# Minimum input
assert Solution().maximumImportance(2, [[0,1]]) == 3  # only two cities

# Sparse roads
assert Solution().maximumImportance(4, [[0,1]]) == 7