#2285

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Maximum Total Importance of Roads

Assign unique values to cities to maximize the total importance of all roads using greedy selection based on city connectivity.

greedy graph sorting heap priority queue

Problem Statement

You are given a country with 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, representing its importance.

The importance of a road is the sum of the values of the two cities it connects. Your task is to determine the assignment of city values that maximizes the sum of importance of all roads, considering constraints that each value is used exactly once and all roads are counted.

Examples

Example 1

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

Output: 43

The figure above shows the country and the assigned values of [2,4,5,3,1].

The road (0,1) has an importance of 2 + 4 = 6.
The road (1,2) has an importance of 4 + 5 = 9.
The road (2,3) has an importance of 5 + 3 = 8.
The road (0,2) has an importance of 2 + 5 = 7.
The road (1,3) has an importance of 4 + 3 = 7.
The road (2,4) has an importance of 5 + 1 = 6. The total importance of all roads is 6 + 9 + 8 + 7 + 7 + 6 = 43. It can be shown that we cannot obtain a greater total importance than 43.

Example 2

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

Output: 20

The figure above shows the country and the assigned values of [4,3,2,5,1].

The road (0,3) has an importance of 4 + 5 = 9.
The road (2,4) has an importance of 2 + 1 = 3.
The road (1,3) has an importance of 3 + 5 = 8. The total importance of all roads is 9 + 3 + 8 = 20. It can be shown that we cannot obtain a greater total importance than 20.

Constraints

2 <= n <= 5 * 104
1 <= roads.length <= 5 * 104
roads[i].length == 2
0 <= ai, bi <= n - 1
ai != bi
There are no duplicate roads.

Solution Approach

Count connections for greedy ranking

Compute the degree of each city, which is the number of roads it connects to. Cities with higher degrees have greater potential impact on total importance.

Assign values in descending order

Sort cities by degree in descending order and assign values from n down to 1. This greedy choice ensures cities contributing to more roads get higher values.

Compute total road importance

Iterate through each road, summing the assigned values of its endpoints. Validate that no higher total can be achieved without breaking the unique value constraint.

Complexity Analysis

Metric	Value
Time	O(N^2)
Space	O(N)

Time complexity is O(N + M + N log N) where N is the number of cities and M is the number of roads, dominated by sorting cities. Space complexity is O(N) for storing degrees and assignments.

What Interviewers Usually Probe

Expect discussion of greedy strategies based on city degree.
Look for correct handling of unique assignment constraints.
Check reasoning about why assigning top values to most connected cities maximizes importance.

Common Pitfalls or Variants

Common pitfalls

Assigning values without considering city degree leads to suboptimal total importance.
Ignoring the uniqueness constraint can produce invalid assignments.
Failing to correctly sum both endpoints of each road causes miscalculation of total importance.

Follow-up variants

Minimize total importance instead of maximizing it by reversing value assignment.
Allow multiple roads between cities and compute maximum total importance accordingly.
Use weighted roads where each road has a factor, adjusting the greedy ranking by weighted degree.

FAQ

What is the main pattern used in Maximum Total Importance of Roads?

The primary pattern is greedy choice plus invariant validation, assigning highest values to cities with the most connections.

How do I handle the uniqueness of city values?

Assign values from n down to 1 in descending order based on city degree to guarantee each value is used once.

Can this approach handle large numbers of cities efficiently?

Yes, computing degrees and sorting cities allows handling up to tens of thousands of cities within reasonable time and space limits.

What if two cities have the same degree?

Ties can be broken arbitrarily; the greedy pattern still ensures a maximum total importance since all high-degree cities receive top values.

How is the total road importance calculated?

Sum the values of both endpoints for each road after assigning all city values; this ensures the total importance reflects the greedy assignment.

terminal

Solution

Solution 1: Greedy + Sorting

We consider the contribution of each city to the total importance of all roads, recorded in the array $\textit{deg}$. Then, we sort $\textit{deg}$ by contribution from smallest to largest and allocate $[1, 2, ..., n]$ to the cities in order.

1

2

3

4

5

6

7

8

class Solution:
    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:
        deg = [0] * n
        for a, b in roads:
            deg[a] += 1
            deg[b] += 1
        deg.sort()
        return sum(i * v for i, v in enumerate(deg, 1))

Continue Practicing

#2497 maximum star sum of a graph #2333 minimum sum of squared difference #2335 minimum amount of time to fill cups