Minimum Number of Work Sessions to Finish the Tasks

Medium
1048.

Minimum Number of Work Sessions to Finish the Tasks

Minimum Number of Work Sessions to Finish the Tasks is a medium coding problem on arrays, dynamic programming and bit manipulation, asked in Amazon, Google and Microsoft interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} tasks
 * @param {number} sessionTime
 * @return {number}
 */
var minSessions = function(tasks, sessionTime) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Number of Work Sessions to Finish the Tasks Solution

Minimum Number of Work Sessions to Finish the Tasks solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Number of Work Sessions to Finish the Tasks is a medium coding problem on arrays, dynamic programming and bit manipulation, asked in Amazon, Google and Microsoft interviews.

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

Hints for Minimum Number of Work Sessions to Finish the Tasks

  1. Hint 1

    n <= 14, which is the signature of a bitmask over the set of finished tasks.

  2. Hint 2

    A state needs two numbers: how many sessions are used, and how much time is left in the current one.

  3. Hint 3

    Prefer fewer sessions; among equal session counts prefer more time remaining.

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

  1. Start at mask = 0 with one empty session open: sessions = 1, left = sessionTime.
  2. 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.
  3. Keep the better pair at mask | (1 << i).
  4. 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]

Java

public static int minSessions(int[] tasks, int sessionTime) {
    int n = tasks.length;
    int full = 1 << n;
    final int INF = 1000000;
    int[] sessions = new int[full];
    int[] left = new int[full];
    Arrays.fill(sessions, INF);
    sessions[0] = 1;
    left[0] = sessionTime;
    for (int mask = 0; mask < full; mask++) {
        if (sessions[mask] == INF) continue;
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) continue;
            int s, l;
            if (left[mask] >= tasks[i]) {
                s = sessions[mask];
                l = left[mask] - tasks[i];
            } else {
                s = sessions[mask] + 1;
                l = sessionTime - tasks[i];
            }
            int next = mask | (1 << i);
            if (s < sessions[next] || (s == sessions[next] && l > left[next])) {
                sessions[next] = s;
                left[next] = l;
            }
        }
    }
    return sessions[full - 1];
}

C++

int minSessions(vector<int>& tasks, int sessionTime) {
    int n = (int) tasks.size();
    int full = 1 << n;
    const int INF = 1000000;
    vector<int> sessions(full, INF), left(full, 0);
    sessions[0] = 1;
    left[0] = sessionTime;
    for (int mask = 0; mask < full; mask++) {
        if (sessions[mask] == INF) continue;
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) continue;
            int s, l;
            if (left[mask] >= tasks[i]) {
                s = sessions[mask];
                l = left[mask] - tasks[i];
            } else {
                s = sessions[mask] + 1;
                l = sessionTime - tasks[i];
            }
            int nxt = mask | (1 << i);
            if (s < sessions[nxt] || (s == sessions[nxt] && 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming