2285. Maximum Total Importance of Roads

#define ll long long

class Solution {
public:
    long long maximumImportance(int n, vector<vector<int>>& roads)
    {
        vector<ll> city(n);
        // 計算與多少城市相連
        for(auto road : roads)
        {
            city[road[0]]++;
            city[road[1]]++;
        }

        sort(city.begin(), city.end());

        ll res = 0;
        // city = [1, 2, 2, 3, 4]
        //         1, 2, 3, 4, 5
        //         1 + 4 + 6 + 12 + 20 = 43
        // res += 與多少城市相連 * 城市的數目加權
        for (int i = 0; i < n; ++i)
        {
            res += (i + 1) * city[i];
        }
        return res;
    }
};

• T: $O(N^2)$
• S: $O(N)$