1723.完成所有工作的最短时间

链接：1723.完成所有工作的最短时间
难度：Hard
标签：位运算、数组、动态规划、回溯、状态压缩
简介：返回分配方案中尽可能 最小 的 最大工作时间 。

题解 1 - typescript

• 编辑时间：2021-05-08
• 执行用时：3336ms
• 内存消耗：39.8MB
• 编程语言：typescript
• 解法介绍：回溯。

function minimumTimeRequired(jobs: number[], k: number): number {
  const len = jobs.length;
  if (len === k) return Math.max(...jobs);
  const workers: number[] = new Array(k).fill(0);
  let min = Infinity;
  const distribute = (jobIndex: number = 0) => {
    if (jobIndex === len) {
      min = Math.min(min, Math.max(...workers));
      return;
    }
    for (let i = 0; i < k; i++) {
      if (i > 0 && workers[i] === workers[i - 1]) continue;
      workers[i] += jobs[jobIndex];
      distribute(jobIndex + 1);
      workers[i] -= jobs[jobIndex];
    }
  };
  distribute();
  return min;
}