Minimum Number of Work Sessions to Finish the Tasks — Medium Problem & Solution

tasks[i] is how many hours task i takes. You work in sessions of at most sessionTime consecutive hours.

Difficulty: Medium
Topics: Arrays, Dynamic Programming, Bit Manipulation, Backtracking, Bitmask
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

tasks[i] is how many hours task i takes. You work in sessions of at most sessionTime consecutive hours. A task must be finished within a single session — it cannot be split — and tasks may be done in any order.

Return the minimum number of sessions needed to finish every task.

Example 1

Input: tasks = [1,2,3], sessionTime = 3
Output: 2
Explanation: Session 1 does tasks 0 and 1; session 2 does task 2.

Example 2

Input: tasks = [3,1,3,1,1], sessionTime = 8
Output: 2
Explanation: 3 + 3 + 1 in the first, 1 + 1 in the second.

Example 3

Input: tasks = [1,2,3,4,5], sessionTime = 15
Output: 1
Explanation: Everything fits in one session.

Constraints

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

How to solve Minimum Number of Work Sessions to Finish the Tasks

Bitmask DP over the set of completed tasks. For each state store the pair (sessions used, time left in the current session) and keep the lexicographically best — fewer sessions first, then more time remaining. Adding a task either fits in the current session or opens a new one.

Approach

Start at mask = 0 with one empty session open: sessions = 1, left = sessionTime.
For each reachable mask and each unfinished task i: if left >= tasks[i] stay in the session and subtract; otherwise start a new session with sessionTime - tasks[i] left.
Keep the better pair at mask | (1 << i).
Return the session count at the full mask.

Why it works

Storing (sessions, left) and comparing lexicographically is what makes the greedy inside the DP sound: for a fixed set of completed tasks, fewer sessions is always at least as good, and at equal sessions more remaining time can only widen the options ahead. Without the tie-break the DP would keep an arbitrary representative of a state and miss optimal continuations.

Complexity

Time — O(2ⁿ · n)
Space — O(2ⁿ)

Pitfalls

A state is not just the session count — two ways to reach the same mask can leave very different amounts of time.
The initial state has one session already open, not zero.
Tasks cannot be split across sessions, which is what rules out a simple bin-packing greedy.

Reference solution

Python

from typing import List

def minSessions(tasks: List[int], sessionTime: int) -> int:
    n = len(tasks)
    full = 1 << n
    INF = 10**6
    sessions = [INF] * full
    left = [0] * full
    sessions[0] = 1
    left[0] = sessionTime
    for mask in range(full):
        if sessions[mask] == INF:
            continue
        for i in range(n):
            if mask & (1 << i):
                continue
            if left[mask] >= tasks[i]:
                s, l = sessions[mask], left[mask] - tasks[i]
            else:
                s, l = sessions[mask] + 1, sessionTime - tasks[i]
            nxt = mask | (1 << i)
            if s < sessions[nxt] or (s == sessions[nxt] and l > left[nxt]):
                sessions[nxt] = s
                left[nxt] = l
    return sessions[full - 1]

JavaScript

var minSessions = function(tasks, sessionTime) {
    var n = tasks.length, full = 1 << n, INF = 1000000, m, i;
    var sessions = [], left = [];
    for (m = 0; m < full; m++) { sessions.push(INF); left.push(0); }
    sessions[0] = 1;
    left[0] = sessionTime;
    for (m = 0; m < full; m++) {
        if (sessions[m] === INF) continue;
        for (i = 0; i < n; i++) {
            if (m & (1 << i)) continue;
            var s, l;
            if (left[m] >= tasks[i]) { s = sessions[m]; l = left[m] - tasks[i]; }
            else { s = sessions[m] + 1; l = sessionTime - tasks[i]; }
            var next = m | (1 << i);
            if (s < sessions[next] || (s === sessions[next] && l > left[next])) {
                sessions[next] = s;
                left[next] = l;
            }
        }
    }
    return sessions[full - 1];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue