2285 - Maximum Total Importance of Roads

 C++

• class Solution {
  public:
      long long maximumImportance(int n, vector<vector<int>>& roads) {
          vector<int> deg(n);
          for (auto& r : roads) {
              ++deg[r[0]];
              ++deg[r[1]];
          }
          sort(deg.begin(), deg.end());
          long long ans = 0;
          for (int i = 0; i < n; ++i) ans += 1ll * (i + 1) * deg[i];
          return ans;
      }
  };

JAVA

class Solution {
    public long maximumImportance(int n, int[][] roads) {
        int[] degree = new int[n];
        int maxdegree = 0;
        for (int[] r : roads) {
            degree[r[0]]++;
            degree[r[1]]++;
            maxdegree = Math.max(maxdegree, Math.max(degree[r[0]], degree[r[1]]));
        }
        Map<Integer, Integer> rank = new HashMap<>();
        int i = n;
        while (i > 0) {
            for (int j = 0; j < n; j++) {
                if (degree[j] == maxdegree) {
                    rank.put(j, i--);
                    degree[j] = Integer.MIN_VALUE;
                }
            }
            maxdegree = 0;
            for (int d : degree) {
                maxdegree = Math.max(maxdegree, d);
            }
        }
        long res = 0;
        for (int[] r : roads) {
            res += rank.get(r[0]) + rank.get(r[1]);
        }
        return res;
    }
}