_2285. Maximum Total Importance of Roads.md

2285. Maximum Total Importance of Roads

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 28, 2024

Last updated : June 28, 2024

---

Related Topics : Greedy, Graph, Sorting, Heap (Priority Queue)

Acceptance Rate : 69.29 %

---

Solutions

• m2285 Daily.py
• m2285 v2.py
• m2285 v2.c
• m2285 v2.cpp
• m2285 v2.java

Python

m2285 Daily.py

class Solution:
    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:
        cnt = Counter([roads[x // 2][x % 2] for x in range(len(roads) * 2)])
        validVals = sorted(list(cnt.values()))

        i = n
        output = 0

        while validVals :
            output += i * validVals.pop()
            i -= 1

        return output

m2285 v2.py

class Solution:
    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:
        cnt = [0] * n
        for road in roads :
            cnt[road[0]] += 1
            cnt[road[1]] += 1
        cnt.sort()

        i = n
        output = 0

        while cnt and cnt[-1] > 0 :
            output += i * cnt.pop()
            i -= 1

        return output

C

m2285 v2.c

int compare(const void* a, const void* b) {
    return *((int*) a) - *((int*) b);
}

long long maximumImportance(int n, int** roads, int roadsSize, int* roadsColSize) {
    int cnt[n];
        memset(&cnt, 0, n * sizeof(int));

        for (int i = 0; i < roadsSize; i++) {
            cnt[roads[i][0]]++;
            cnt[roads[i][1]]++;
        }

        qsort(cnt, n, sizeof(int), compare);

        long long output = 0;
        for (int i = n; i > 0 && cnt[i - 1] > 0; i--) {
            output += (long long) i * (long long) cnt[i - 1];
        }
        return output;
}

C++

m2285 v2.cpp

class Solution {
public:
    long long maximumImportance(int n, vector<vector<int>>& roads) {
        int cnt[n];
        memset(&cnt, 0, n * sizeof(int));

        for (int i = 0; i < roads.size(); i++) {
            cnt[roads[i][0]]++;
            cnt[roads[i][1]]++;
        }
        sort(cnt, cnt + n);

        long long output = 0;
        for (int i = n; i > 0 && cnt[i - 1] > 0; i--) {
            output += (long long) i * (long long) cnt[i - 1];
        }
        return output;
    }
};

Java

m2285 v2.java

class Solution {
    public long maximumImportance(int n, int[][] roads) {
        int[] cnt = new int[n];

        for (int[] road : roads) {
            cnt[road[0]]++;
            cnt[road[1]]++;
        }
        Arrays.sort(cnt);

        long output = 0;
        for (int i = n; i > 0 && cnt[i - 1] > 0; i--) {
            output += ((long) i * (long) cnt[i - 1]);
        }
        return output;
    }
}