Minimum Number of Work Sessions to Finish the Tasks

Problem

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 theminimum 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].

Examples

Example 1

1
2
3
4
5


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

1
2
3
4
5


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

1
2
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

Solution

Method 1 – Bitmask DP

Intuition

We want to partition tasks into the minimum number of sessions, each with total time ≤ sessionTime. Try all possible groupings using bitmask DP, where each state represents a subset of tasks.

Approach

Use DP where dp[mask] is the minimum sessions needed for tasks in mask.
For each mask, try all possible submasks that fit in one session.
For each valid submask, update dp[mask] = min(dp[mask], dp[mask ^ submask] + 1).
Precompute the sum of times for all masks.
The answer is dp[full_mask].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    int minSessions(vector<int>& tasks, int sessionTime) {
        int n = tasks.size(), N = 1 << n;
        vector<int> sum(N, 0), dp(N, n);
        for (int mask = 1; mask < N; ++mask)
            for (int i = 0; i < n; ++i)
                if (mask & (1 << i)) sum[mask] += tasks[i];
        dp[0] = 0;
        for (int mask = 1; mask < N; ++mask) {
            for (int sub = mask; sub; sub = (sub - 1) & mask) {
                if (sum[sub] <= sessionTime)
                    dp[mask] = min(dp[mask], dp[mask ^ sub] + 1);
            }
        }
        return dp[N - 1];
    }
};

 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


func minSessions(tasks []int, sessionTime int) int {
    n := len(tasks)
    N := 1 << n
    sum := make([]int, N)
    dp := make([]int, N)
    for i := range dp {
        dp[i] = n
    }
    for mask := 1; mask < N; mask++ {
        for i := 0; i < n; i++ {
            if mask&(1<<i) > 0 {
                sum[mask] += tasks[i]
            }
        }
    }
    dp[0] = 0
    for mask := 1; mask < N; mask++ {
        for sub := mask; sub > 0; sub = (sub - 1) & mask {
            if sum[sub] <= sessionTime {
                if dp[mask^sub]+1 < dp[mask] {
                    dp[mask] = dp[mask^sub] + 1
                }
            }
        }
    }
    return dp[N-1]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


import java.util.*;
class Solution {
    public int minSessions(int[] tasks, int sessionTime) {
        int n = tasks.length, N = 1 << n;
        int[] sum = new int[N], dp = new int[N];
        Arrays.fill(dp, n);
        for (int mask = 1; mask < N; ++mask)
            for (int i = 0; i < n; ++i)
                if ((mask & (1 << i)) > 0) sum[mask] += tasks[i];
        dp[0] = 0;
        for (int mask = 1; mask < N; ++mask)
            for (int sub = mask; sub > 0; sub = (sub - 1) & mask)
                if (sum[sub] <= sessionTime)
                    dp[mask] = Math.min(dp[mask], dp[mask ^ sub] + 1);
        return dp[N - 1];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
    fun minSessions(tasks: IntArray, sessionTime: Int): Int {
        val n = tasks.size
        val N = 1 shl n
        val sum = IntArray(N)
        val dp = IntArray(N) { n }
        for (mask in 1 until N)
            for (i in 0 until n)
                if ((mask shr i) and 1 == 1) sum[mask] += tasks[i]
        dp[0] = 0
        for (mask in 1 until N)
            var sub = mask
            while (sub > 0) {
                if (sum[sub] <= sessionTime)
                    dp[mask] = minOf(dp[mask], dp[mask xor sub] + 1)
                sub = (sub - 1) and mask
            }
        return dp[N - 1]
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution:
    def minSessions(self, tasks: list[int], sessionTime: int) -> int:
        n = len(tasks)
        N = 1 << n
        sum_mask = [0] * N
        dp = [n] * N
        for mask in range(1, N):
            for i in range(n):
                if mask & (1 << i):
                    sum_mask[mask] += tasks[i]
        dp[0] = 0
        for mask in range(1, N):
            sub = mask
            while sub:
                if sum_mask[sub] <= sessionTime:
                    dp[mask] = min(dp[mask], dp[mask ^ sub] + 1)
                sub = (sub - 1) & mask
        return dp[N - 1]

 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


impl Solution {
    pub fn min_sessions(tasks: Vec<i32>, session_time: i32) -> i32 {
        let n = tasks.len();
        let N = 1 << n;
        let mut sum = vec![0; N];
        let mut dp = vec![n as i32; N];
        for mask in 1..N {
            for i in 0..n {
                if (mask & (1 << i)) > 0 {
                    sum[mask] += tasks[i];
                }
            }
        }
        dp[0] = 0;
        for mask in 1..N {
            let mut sub = mask;
            while sub > 0 {
                if sum[sub] <= session_time {
                    dp[mask] = dp[mask].min(dp[mask ^ sub] + 1);
                }
                sub = (sub - 1) & mask;
            }
        }
        dp[N - 1]
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
    minSessions(tasks: number[], sessionTime: number): number {
        const n = tasks.length;
        const N = 1 << n;
        const sum = Array(N).fill(0);
        const dp = Array(N).fill(n);
        for (let mask = 1; mask < N; ++mask)
            for (let i = 0; i < n; ++i)
                if (mask & (1 << i)) sum[mask] += tasks[i];
        dp[0] = 0;
        for (let mask = 1; mask < N; ++mask) {
            for (let sub = mask; sub > 0; sub = (sub - 1) & mask) {
                if (sum[sub] <= sessionTime)
                    dp[mask] = Math.min(dp[mask], dp[mask ^ sub] + 1);
            }
        }
        return dp[N - 1];
    }
}

Complexity

⏰ Time complexity: O(n * 2^n) — For each mask, we try all submasks, n ≤ 14.
🧺 Space complexity: O(2^n) — For DP and sum arrays.

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 – Bitmask DP#

Intuition#

Approach#

Code#

Complexity#