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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Total Importance of Roads

Difficulty: Medium

Problem Description

You are given an integer n denoting the number of cities in a country. The cities are numbered from 0 to n - 1. You are also given a 2D integer array roads where roads[i] = [ai, bi] denotes that there exists a bidirectional road connecting cities ai and bi. You need to assign each city with an integer value from 1 to n, where each value can only be used once. The importance of a road is then defined as the sum of the values of the two cities it connects. Return the maximum total importance of all roads possible after assigning the values optimally.

Key Insights

  • The importance of a road connecting two cities is the sum of the assigned values of those cities.
  • To maximize the total importance, cities with a higher number of connections (degree) should be assigned higher values.
  • The problem can be approached by calculating the degree of each city and then assigning the available values from n down to 1 based on the degree.

Space and Time Complexity

Time Complexity: O(m + n) where m is the number of roads and n is the number of cities.
Space Complexity: O(n) for storing the degree of each city.

Solution

To solve this problem, we utilize the following steps:

  1. Build a degree array to count the number of connections for each city.
  2. Sort the cities based on their degree in descending order.
  3. Assign values from n down to 1 to the cities based on their rank after sorting.
  4. Calculate the total importance by summing the importance of each road using the assigned values.

The primary data structure used is an array to keep track of the degrees of each city, and we also perform sorting based on these degrees to determine the assignment of values.

Code Solutions

def maximumImportance(n, roads):
    # Step 1: Initialize a degree array
    degree = [0] * n
    
    # Step 2: Count the degree of each city
    for a, b in roads:
        degree[a] += 1
        degree[b] += 1
    
    # Step 3: Sort cities by degree
    degree.sort(reverse=True)
    
    # Step 4: Assign values from n to 1 based on sorted degrees
    importance = 0
    for i in range(n):
        importance += degree[i] * (i + 1)
    
    return importance
← Back to All Questions