1986. Minimum Number of Work Sessions to Finish the Tasks LeetCode Solution
In this guide, you will get 1986. Minimum Number of Work Sessions to Finish the Tasks LeetCode Solution with the best time and space complexity. The solution to Minimum Number of Work Sessions to Finish the Tasks problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Number of Work Sessions to Finish the Tasks
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].
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
Complexity Analysis
Time Complexity: O(n \cdot 2^n)
Space Complexity: O(n \cdot 2^n)
1986. Minimum Number of Work Sessions to Finish the Tasks LeetCode Solution in C++
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;
}
}; /* code provided by PROGIEZ */
1986. Minimum Number of Work Sessions to Finish the Tasks LeetCode Solution in Java
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;
}
} // code provided by PROGIEZ
1986. Minimum Number of Work Sessions to Finish the Tasks LeetCode Solution in Python
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 # code by PROGIEZ
