2285. Maximum Total Importance of Roads

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    long long maximumImportance(int n, vector<vector<int>>& roads) {
        // 最多連結的給最大，然後遞減
        vector<int> vec(n,0);
        vector<pair<int, int> > arr;
        unordered_map<int,int> memo;
        long long ret= 0;
        
        for(auto road:roads){
            vec[road[0]]++;
            vec[road[1]]++;
        }
        for(int i=0;i<n;++i){
            arr.push_back(make_pair(i,vec[i]));
        }
        sort(arr.begin(), arr.end(), [](auto &a, auto &b){
            return a.second>b.second;
        });
        int cur =n;
        for(auto &[a,b]:arr){
            b = cur--;
            memo[a] = b;
        }
        for(auto road:roads){
            ret+= memo[road[0]]+memo[road[1]];
        }
        
        return ret;
        
    }
};

analysis

  • time complexity O(nlogn)