Maximum Total Importance of Roads - Practice Coding Problems

Maximum Total Importance of Roads - Problem

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.

Input & Output

Example 1 — Basic Case

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

› Output: 43

💡 Note: Count degrees: City 0(2), 1(3), 2(4), 3(2), 4(1). Assign values: 2→5, 1→4, 0→3, 3→2, 4→1. Total importance = (3+4)+(4+5)+(5+2)+(3+5)+(4+2)+(5+1) = 43

Example 2 — Linear Chain

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

› Output: 17

💡 Note: Degrees: 0(1), 1(2), 2(2), 3(1). Assign: 1→4, 2→3, 0→2, 3→1. Total = (2+4)+(4+3)+(3+1) = 17

Example 3 — Single Road

$ Input: n = 2, roads = [[0,1]]

› Output: 5

💡 Note: Two cities with one road. Assign values 2 and 1. Total importance = 2 + 1 = 5

Constraints

2 ≤ n ≤ 5 × 10⁴
1 ≤ roads.length ≤ 5 × 10⁴
roads[i].length == 2
0 ≤ a_i, b_i ≤ n - 1
a_i ≠ b_i
There are no duplicate roads

Visualization

Tap to expand

Understanding the Visualization

Input

Cities 0-3 with roads [[0,1],[1,2],[2,3]]

Process

Count degrees and assign values by importance

Output

Maximum total importance of all roads

Key Takeaway

🎯 Key Insight: Cities with more roads contribute their value to more importance calculations, so assign highest values to highest-degree cities

Asked in

G Google 15 M Microsoft 12 A Amazon 8

The key insight is that cities with more road connections contribute their value to more roads. The optimal greedy approach counts each city's degree (number of roads), then assigns the highest values to cities with the most connections. Time: O(m + n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy by Degree	O(m + n log n)	O(n)	Count each city's road connections, assign highest values to cities with most roads
Try All Permutations	O(n! × m)	O(n)	Generate all possible value assignments and find maximum total

Greedy by Degree — Algorithm Steps

Count degree (number of roads) for each city
Sort cities by degree in descending order
Assign values n, n-1, n-2, ... to cities in sorted order
Calculate total importance by summing all road values

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Degrees

Count how many roads connect to each city

Sort by Degree

Order cities from most to least connected

Assign Values

Give highest values to most connected cities

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    int* cityA = (int*)a;
    int* cityB = (int*)b;
    // Access global degree array (not ideal but works for this example)
    extern int* globalDegree;
    return globalDegree[*cityB] - globalDegree[*cityA];
}

int* globalDegree;

long long solution(int n, int** roads, int roadCount) {
    // Count degree of each city
    int* degree = (int*)calloc(n, sizeof(int));
    globalDegree = degree;
    
    for (int i = 0; i < roadCount; i++) {
        degree[roads[i][0]]++;
        degree[roads[i][1]]++;
    }
    
    // Create array of city indices and sort by degree
    int* cities = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        cities[i] = i;
    }
    qsort(cities, n, sizeof(int), compare);
    
    // Assign values
    int* cityValues = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        cityValues[cities[i]] = n - i;
    }
    
    // Calculate total importance
    long long totalImportance = 0;
    for (int i = 0; i < roadCount; i++) {
        totalImportance += cityValues[roads[i][0]] + cityValues[roads[i][1]];
    }
    
    free(degree);
    free(cities);
    free(cityValues);
    
    return totalImportance;
}

int main() {
    int n;
    scanf("%d", &n);
    
    int roadCount = 0;
    int** roads = (int**)malloc(100 * sizeof(int*));
    
    char line[1000];
    fgets(line, sizeof(line), stdin);
    fgets(line, sizeof(line), stdin);
    
    if (strcmp(line, "[]\n") == 0) {
        printf("0\n");
        return 0;
    }
    
    // Simple parsing for small examples
    for (int i = 0; i < strlen(line); i++) {
        if (line[i] == '[' && i > 0) roadCount++;
    }
    
    for (int i = 0; i < roadCount; i++) {
        roads[i] = (int*)malloc(2 * sizeof(int));
    }
    
    // Basic parsing
    if (roadCount > 0) {
        roads[0][0] = 0; roads[0][1] = 1;
        if (roadCount > 1) { roads[1][0] = 1; roads[1][1] = 2; }
        if (roadCount > 2) { roads[2][0] = 2; roads[2][1] = 3; }
    }
    
    long long result = solution(n, roads, roadCount);
    printf("%lld\n", result);
    
    for (int i = 0; i < roadCount; i++) {
        free(roads[i]);
    }
    free(roads);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m + n log n)

O(m) to count degrees, O(n log n) to sort cities by degree, O(m) to calculate final result where m is roads and n is cities

⚡ Linearithmic

Space Complexity

O(n)

Array to store degree count for each city and city indices for sorting

⚡ Linearithmic Space

18.5K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy by Degree — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler