Skip to content

1986. Minimum Number of Work Sessions to Finish the Tasks 👍

  • Time: $O(n \cdot 2^n)$
  • Space: $O(n \cdot 2^n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
 public:
  int minSessions(vector<int>& tasks, int sessionTime) {
    for (int numSessions = 1; numSessions <= tasks.size(); ++numSessions)
      if (dfs(tasks, 0, vector<int>(numSessions), sessionTime))
        return numSessions;
    throw;
  }

  // Returns true if we can assign tasks[s..n) to `sessions`. Note that
  // `sessions` may be occupied by some tasks.
  bool dfs(const vector<int>& tasks, int s, vector<int>&& sessions,
           const int& sessionTime) {
    if (s == tasks.size())
      return true;

    for (int& session : sessions) {
      // Can't assign the tasks[s] to this session.
      if (session + tasks[s] > sessionTime)
        continue;
      // Assign the tasks[s] to this session.
      session += tasks[s];
      if (dfs(tasks, s + 1, std::move(sessions), sessionTime))
        return true;
      // Backtracking.
      session -= tasks[s];
      // If it's the first time we assign the tasks[s] to this session, then
      // future `session`s can't satisfy either.
      if (session == 0)
        return false;
    }

    return false;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
  public int minSessions(int[] tasks, int sessionTime) {
    for (int numSessions = 1; numSessions <= tasks.length; ++numSessions)
      if (dfs(tasks, 0, new int[numSessions], sessionTime))
        return numSessions;
    throw new IllegalArgumentException();
  }

  // Returns true if we can assign tasks[s..n) to `sessions`. Note that `sessions`
  // may be occupied by some tasks.
  private boolean dfs(int[] tasks, int s, int[] sessions, int sessionTime) {
    if (s == tasks.length)
      return true;

    for (int i = 0; i < sessions.length; ++i) {
      // Can't assign the tasks[s] to this session.
      if (sessions[i] + tasks[s] > sessionTime)
        continue;
      // Assign the tasks[s] to this session.
      sessions[i] += tasks[s];
      if (dfs(tasks, s + 1, sessions, sessionTime))
        return true;
      // Backtracking.
      sessions[i] -= tasks[s];
      // If it's the first time we assign the tasks[s] to this session, then future
      // `session`s can't satisfy either.
      if (sessions[i] == 0)
        return false;
    }

    return false;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
  def minSessions(self, tasks: list[int], sessionTime: int) -> int:
    # Returns True if we can assign tasks[s..n) to `sessions`. Note that `sessions`
    # may be occupied by some tasks.
    def dfs(s: int, sessions: list[int]) -> bool:
      if s == len(tasks):
        return True

      for i, session in enumerate(sessions):
        # Can't assign the tasks[s] to this session.
        if session + tasks[s] > sessionTime:
          continue
        # Assign the tasks[s] to this session.
        sessions[i] += tasks[s]
        if dfs(s + 1, sessions):
          return True
        # Backtracking.
        sessions[i] -= tasks[s]
        # If it's the first time we assign the tasks[s] to this session, then future
        # `session`s can't satisfy either.
        if sessions[i] == 0:
          return False

      return False

    for numSessions in range(1, len(tasks) + 1):
      if dfs(0, [0] * numSessions):
        return numSessions