We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Total Importance of Roads

Number: 2379

Difficulty: Medium

Paid? No

Companies: Microsoft, Amazon, Hudson River Trading

Problem Description

We are given n cities (numbered from 0 to n - 1) and a list of bidirectional roads connecting these cities. We need to assign each city a unique value from 1 to n. The importance of a road is the sum of the values assigned to the two cities it connects. Our goal is to maximize the total importance of all roads after an optimal assignment.

Key Insights

  • The contribution of a city to the total importance is proportional to its degree (the number of roads connected to that city).
  • To maximize the total importance, assign higher values to cities with higher degrees.
  • The overall maximum importance can be computed as the sum for all cities of (assigned value * city degree).
  • Greedy strategy: sort cities by degree and assign values in descending order from n to 1.

Space and Time Complexity

Time Complexity: O(n + m + n log n)

  • O(n) to initialize and count degrees.
  • O(m) to process the roads.
  • O(n log n) to sort the cities by their degree. Space Complexity: O(n)
  • We store the degree for each of the n cities.

Solution

We begin by calculating the degree for each city based on the given roads. Once we have the degree counts, we sort the cities by their degrees in ascending order. Then we assign the highest value (n) to the city with the highest degree, the next highest (n - 1) to the city with the second highest degree, and so on. Finally, we compute the total importance by multiplying each city’s degree with the assigned value and summing up these products. This greedy assignment ensures that cities contributing more (with higher degrees) receive higher values, maximizing the overall sum.

Code Solutions

# Python Solution

def maximumImportance(n, roads):
    # Initialize degrees for each city
    degrees = [0] * n
    
    # Count the degree for each city based on the roads list
    for a, b in roads:
        degrees[a] += 1
        degrees[b] += 1
    
    # Sort the degrees in ascending order
    degrees.sort()
    
    # Maximum importance is maximizing the weighted sum:
    # Multiply each sorted degree with the corresponding assigned value (from 1 to n)
    total_importance = 0
    for i in range(n):
        total_importance += degrees[i] * (i + 1)
    
    return total_importance

# Example usage:
n = 5
roads = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]
print(maximumImportance(n, roads))  # Expected output: 43
← Back to All Questions