Question

1986. Minimum Number of Work Sessions to Finish the Tasks

中文文档

Description

There are n tasks assigned to you. The task times are represented as an integer array tasks of length n, where the ith task takes tasks[i] hours to finish. A work session is when you work for at most sessionTime consecutive hours and then take a break.

You should finish the given tasks in a way that satisfies the following conditions:

• If you start a task in a work session, you must complete it in the same work session.
• You can start a new task immediately after finishing the previous one.
• You may complete the tasks in any order.

Given tasks and sessionTime, return _the minimum number of work sessions needed to finish all the tasks following the conditions above._

The tests are generated such that sessionTime is greater than or equal to the maximum element in tasks[i].

 

Example 1:

Input: tasks = [1,2,3], sessionTime = 3
Output: 2
Explanation: You can finish the tasks in two work sessions.
- First work session: finish the first and the second tasks in 1 + 2 = 3 hours.
- Second work session: finish the third task in 3 hours.

Example 2:

Input: tasks = [3,1,3,1,1], sessionTime = 8
Output: 2
Explanation: You can finish the tasks in two work sessions.
- First work session: finish all the tasks except the last one in 3 + 1 + 3 + 1 = 8 hours.
- Second work session: finish the last task in 1 hour.

Example 3:

Input: tasks = [1,2,3,4,5], sessionTime = 15
Output: 1
Explanation: You can finish all the tasks in one work session.

 

Constraints:

• n == tasks.length
• 1 <= n <= 14
• 1 <= tasks[i] <= 10
• max(tasks[i]) <= sessionTime <= 15

Solutions

Solution 1

class Solution:
  def minSessions(self, tasks: List[int], sessionTime: int) -> int:
    n = len(tasks)
    ok = [False] * (1 << n)
    for i in range(1, 1 << n):
      t = sum(tasks[j] for j in range(n) if i >> j & 1)
      ok[i] = t <= sessionTime
    f = [inf] * (1 << n)
    f[0] = 0
    for i in range(1, 1 << n):
      j = i
      while j:
        if ok[j]:
          f[i] = min(f[i], f[i ^ j] + 1)
        j = (j - 1) & i
    return f[-1]

class Solution {
  public int minSessions(int[] tasks, int sessionTime) {
    int n = tasks.length;
    boolean[] ok = new boolean[1 << n];
    for (int i = 1; i < 1 << n; ++i) {
      int t = 0;
      for (int j = 0; j < n; ++j) {
        if ((i >> j & 1) == 1) {
          t += tasks[j];
        }
      }
      ok[i] = t <= sessionTime;
    }
    int[] f = new int[1 << n];
    Arrays.fill(f, 1 << 30);
    f[0] = 0;
    for (int i = 1; i < 1 << n; ++i) {
      for (int j = i; j > 0; j = (j - 1) & i) {
        if (ok[j]) {
          f[i] = Math.min(f[i], f[i ^ j] + 1);
        }
      }
    }
    return f[(1 << n) - 1];
  }
}

class Solution {
public:
  int minSessions(vector<int>& tasks, int sessionTime) {
    int n = tasks.size();
    bool ok[1 << n];
    memset(ok, false, sizeof(ok));
    for (int i = 1; i < 1 << n; ++i) {
      int t = 0;
      for (int j = 0; j < n; ++j) {
        if (i >> j & 1) {
          t += tasks[j];
        }
      }
      ok[i] = t <= sessionTime;
    }
    int f[1 << n];
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    for (int i = 1; i < 1 << n; ++i) {
      for (int j = i; j; j = (j - 1) & i) {
        if (ok[j]) {
          f[i] = min(f[i], f[i ^ j] + 1);
        }
      }
    }
    return f[(1 << n) - 1];
  }
};

func minSessions(tasks []int, sessionTime int) int {
  n := len(tasks)
  ok := make([]bool, 1<<n)
  f := make([]int, 1<<n)
  for i := 1; i < 1<<n; i++ {
    t := 0
    f[i] = 1 << 30
    for j, x := range tasks {
      if i>>j&1 == 1 {
        t += x
      }
    }
    ok[i] = t <= sessionTime
  }
  for i := 1; i < 1<<n; i++ {
    for j := i; j > 0; j = (j - 1) & i {
      if ok[j] {
        f[i] = min(f[i], f[i^j]+1)
      }
    }
  }
  return f[1<<n-1]
}

function minSessions(tasks: number[], sessionTime: number): number {
  const n = tasks.length;
  const ok: boolean[] = new Array(1 << n).fill(false);
  for (let i = 1; i < 1 << n; ++i) {
    let t = 0;
    for (let j = 0; j < n; ++j) {
      if (((i >> j) & 1) === 1) {
        t += tasks[j];
      }
    }
    ok[i] = t <= sessionTime;
  }

  const f: number[] = new Array(1 << n).fill(1 << 30);
  f[0] = 0;
  for (let i = 1; i < 1 << n; ++i) {
    for (let j = i; j > 0; j = (j - 1) & i) {
      if (ok[j]) {
        f[i] = Math.min(f[i], f[i ^ j] + 1);
      }
    }
  }
  return f[(1 << n) - 1];
}