Minimum Number of Work Sessions to Finish the Tasks

Medium Dynamic Programming Bitmask DP Original on LeetCode

Reported atSwiggy

Minimum Number of Work Sessions to Finish the Tasks is a medium dynamic programming problem solved with the bitmask dp pattern. The best approach, optimal (bitmask dp over finished tasks), runs in O(2ⁿ · n) time and O(2ⁿ) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from backtracking (try every session for each task) up.

Problem

You have n tasks, where task i takes tasks[i] hours. You work in sessions: a session is a stretch of at most sessionTime consecutive hours, after which you take a break.

Each task must be finished inside a single session (you cannot split a task across sessions), and once you start a task you finish it before starting another. Tasks may be done in any order, and a session may contain several tasks.

Return the minimum number of sessions needed to finish all the tasks.

Examples

Example 1

Input
tasks = [2, 4, 3], sessionTime = 5
Output
2
Why
One session runs tasks 2 and 3 (5 hours), another runs task 4.

Example 2

Input
tasks = [6, 1, 2, 6], sessionTime = 8
Output
2
Why
Sessions {6, 1} and {6, 2} both fit in 8 hours. One session cannot hold 15 hours.

Example 3

Input
tasks = [3, 3, 3, 3, 3], sessionTime = 7
Output
3
Why
A session fits at most two of these tasks, so five tasks need three sessions.

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Backtracking (try every session for each task)O(nⁿ) worst caseO(n)
Optimal (bitmask DP over finished tasks)O(2ⁿ · n)O(2ⁿ)

1Backtracking (try every session for each task)

TimeO(nⁿ) worst caseEach of the n tasks can go into any of up to n sessions; pruning helps in practice but not in the worst case.
SpaceO(n)The loads array and the recursion stack have size n.

Process tasks one by one. Each task either joins one of the sessions opened so far (if it still fits) or opens a new session. Explore all choices and remember the fewest sessions seen; stop exploring a branch once it already uses as many sessions as the best answer.

  1. Keep an array loads of the current session totals and a variable best = n.
  2. dfs(i, used): if used >= best, stop. If i == n, set best = used.
  3. For each open session j with loads[j] + tasks[i] <= sessionTime, add the task, recurse, then undo.
  4. Also try opening a new session with this task.
class Solution {
    private int[] tasks;
    private int[] loads;
    private int sessionTime;
    private int best;

    public int minSessions(int[] tasks, int sessionTime) {
        this.tasks = tasks;
        this.sessionTime = sessionTime;
        this.loads = new int[tasks.length];
        this.best = tasks.length;
        dfs(0, 0);
        return best;
    }

    private void dfs(int i, int used) {
        if (used >= best) return;
        if (i == tasks.length) {
            best = used;
            return;
        }
        for (int j = 0; j < used; j++) {
            if (loads[j] + tasks[i] <= sessionTime) {
                loads[j] += tasks[i];
                dfs(i + 1, used);
                loads[j] -= tasks[i];
            }
        }
        loads[used] = tasks[i];
        dfs(i + 1, used + 1);
        loads[used] = 0;
    }
}

2Optimal (bitmask DP over finished tasks)

TimeO(2ⁿ · n)Each of the 2ⁿ masks tries each of the n tasks.
SpaceO(2ⁿ)Two arrays of size 2ⁿ.

Let a mask be the set of finished tasks. For each mask keep the best state as a pair: sess[mask] sessions opened and load[mask] hours used in the last one, minimizing sessions first and then load. From a mask, add any unfinished task: if it fits in the current session, the load grows; otherwise a new session opens with just that task. Ordering tasks this way covers every possible packing.

  1. Set sess[0] = 1 and load[0] = 0; every other mask starts at (infinity, infinity).
  2. For each mask in increasing order and each task i not in it, compute the next state: (sess, load + tasks[i]) if it fits, else (sess + 1, tasks[i]).
  3. Keep the smaller pair for mask | (1 << i).
  4. Return sess[full mask].
class Solution {
    public int minSessions(int[] tasks, int sessionTime) {
        int n = tasks.length;
        int full = 1 << n;
        int[] sess = new int[full];
        int[] load = new int[full];
        Arrays.fill(sess, Integer.MAX_VALUE);
        Arrays.fill(load, Integer.MAX_VALUE);
        sess[0] = 1;
        load[0] = 0;
        for (int mask = 0; mask < full; mask++) {
            if (sess[mask] == Integer.MAX_VALUE) continue;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) continue;
                int next = mask | (1 << i);
                int s, l;
                if (load[mask] + tasks[i] <= sessionTime) {
                    s = sess[mask];
                    l = load[mask] + tasks[i];
                } else {
                    s = sess[mask] + 1;
                    l = tasks[i];
                }
                if (s < sess[next] || (s == sess[next] && l < load[next])) {
                    sess[next] = s;
                    load[next] = l;
                }
            }
        }
        return sess[full - 1];
    }
}

Edge cases to test

  • A single task: one session
  • All tasks fit in one session
  • Every task equals sessionTime: one session per task
  • Greedy packing (largest first into the first session that fits) can be suboptimal, so an exact search is needed

Hints

Hint 1

With at most 14 tasks, every subset of tasks can be represented by a bitmask.

Hint 2

For a set of finished tasks, what matters is how many sessions you used and how full the last open session is.

Hint 3

Store for each mask the best pair (sessions used, time used in the current session), comparing sessions first, then time. Extend by adding one unfinished task.

FAQ

What is the best time complexity for Minimum Number of Work Sessions to Finish the Tasks?

Optimal (bitmask DP over finished tasks) runs in O(2ⁿ · n) time and O(2ⁿ) extra space. Each of the 2ⁿ masks tries each of the n tasks.

Which pattern does Minimum Number of Work Sessions to Finish the Tasks use?

It is a dynamic programming problem that uses the bitmask dp pattern. Other problems with the same pattern: Optimal Account Balancing, Smallest Sufficient Team, Frequencies of Shortest Supersequences.

Is there a brute force solution for Minimum Number of Work Sessions to Finish the Tasks?

Yes. Backtracking (try every session for each task) takes O(nⁿ) worst case time and O(n) space. Process tasks one by one.

Which edge cases should I test for Minimum Number of Work Sessions to Finish the Tasks?

A single task: one session; All tasks fit in one session; Every task equals sessionTime: one session per task; Greedy packing (largest first into the first session that fits) can be suboptimal, so an exact search is needed.