求职面试Hacker Rank算法题求助：最小服务器数量计算

这题的核心突破口是所有服务器容量都是2的幂——这个特性让贪心算法成为最优解：更大的2的幂无法被更小的同类组合替代，而且使用更大的服务器能直接减少总数量（比如8的容量等于4+2+2，但只用1台，比3台少）。

解决步骤 #

• 先统计每种容量的服务器有多少台，方便后续快速查询可用数量
• 将所有不同的容量按从大到小排序，优先使用大服务器以最小化数量
• 遍历排序后的容量，计算当前容量最多能使用的台数，累加数量并更新剩余负载
• 最后检查剩余负载是否为0，返回对应结果

JavaScript 实现代码 #

function getMinServers(expected_load, server_array) {
  // 统计各容量服务器的可用数量
  const serverCounts = {};
  for (const s of server_array) {
    serverCounts[s] = (serverCounts[s] || 0) + 1;
  }

  // 按容量从大到小排序
  const sortedServers = Object.keys(serverCounts)
    .map(Number)
    .sort((a, b) => b - a);

  let remainingLoad = expected_load;
  let minServers = 0;

  for (const capacity of sortedServers) {
    if (remainingLoad <= 0) break;
    
    // 计算当前容量最多能使用的台数：不超过剩余负载需求，也不超过可用数量
    const maxNeeded = Math.floor(remainingLoad / capacity);
    const useCount = Math.min(maxNeeded, serverCounts[capacity]);
    
    if (useCount > 0) {
      minServers += useCount;
      remainingLoad -= useCount * capacity;
    }
  }

  return remainingLoad === 0 ? minServers : -1;
}

// 测试示例
console.log(getMinServers(10, [1, 2, 4, 8, 16])); // 输出 2（8 + 2）
console.log(getMinServers(3, [1, 1, 2])); // 输出 2（2 + 1）
console.log(getMinServers(5, [2, 2, 2])); // 输出 -1（无法凑出5）

对你原有代码的分析 #

你之前的嵌套循环只考虑了两台服务器组合的情况，但题目允许任意数量的服务器组合，这种思路会漏掉很多可能的解。而且没有利用2的幂的特性，不仅效率低（O(n²)时间复杂度），也无法保证找到最少数量的解。

内容的提问来源于stack exchange，提问作者Rawle Becerril