Minimum Number of Work Sessions to Finish the Tasks - Problem

You are given n tasks with their respective time requirements in an integer array tasks, where tasks[i] represents the hours needed to complete the i-th task.

A work session allows you to work for at most sessionTime consecutive hours before taking a break. Your goal is to complete all tasks following these rules:

If you start a task in a work session, you must complete it in the same session
You can start a new task immediately after finishing the previous one
You may complete tasks in any order

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

Note: The session time is guaranteed to be at least as large as the maximum task duration.

Input & Output

Example 1 — Basic Case

$ Input: tasks = [1,2,3], sessionTime = 3

› Output: 2

💡 Note: You can finish tasks in 2 sessions: Session 1: [3] (3 hours), Session 2: [1,2] (3 hours total)

Example 2 — More Tasks

$ Input: tasks = [3,1,4], sessionTime = 5

› Output: 2

💡 Note: Optimal grouping: Session 1: [4,1] (5 hours), Session 2: [3] (3 hours). Total: 2 sessions

Example 3 — Perfect Fit

$ Input: tasks = [2,2,2], sessionTime = 4

› Output: 2

💡 Note: Session 1: [2,2] (4 hours), Session 2: [2] (2 hours). Cannot fit all three 2-hour tasks in one 4-hour session

Constraints

1 ≤ tasks.length ≤ 14
1 ≤ tasks[i] ≤ 10
max(tasks[i]) ≤ sessionTime ≤ 15

Visualization

Tap to expand

Asked in

M Meta 15 a Amazon 12 G Google 8 M Microsoft 6

The key insight is to recognize this as a bin packing optimization problem where we want to minimize the number of bins (sessions). The optimal approach uses dynamic programming with bitmasks to represent all possible task combinations and find the minimum partitioning. Time: O(3^n), Space: O(2^n).

Common Approaches

✓ Backtracking (Try All Combinations)

⏱️ Time: O(k^n) Space: O(n)

Use backtracking to explore all possible assignments of tasks to work sessions. For each task, try placing it in existing sessions (if it fits) or create a new session.

Dynamic Programming with Bitmasks

⏱️ Time: O(3^n) Space: O(2^n)

Pre-compute all valid task combinations that fit in one session using bitmasks. Then use DP to find minimum sessions needed to cover all tasks by trying all valid subset combinations.

Backtracking (Try All Combinations) — Algorithm Steps

Sort tasks in descending order for better pruning
For each task, try placing it in each existing session
If task doesn't fit anywhere, start a new session
Track minimum sessions needed

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Tasks

Sort tasks [3,1,4] → [4,3,1] for better pruning

Try Assignments

For each task, try existing sessions or create new one

Find Minimum

Track minimum sessions needed across all valid assignments

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int minSessions;

int compare(const void* a, const void* b) {
    return *(int*)b - *(int*)a;  // Descending order
}

void backtrack(int* tasks, int n, int sessionTime, int* sessions, int sessionCount, int index) {
    if (index == n) {
        if (sessionCount < minSessions) {
            minSessions = sessionCount;
        }
        return;
    }
    
    if (sessionCount >= minSessions) {
        return;
    }
    
    // Try existing sessions
    for (int i = 0; i < sessionCount; i++) {
        if (sessions[i] + tasks[index] <= sessionTime) {
            sessions[i] += tasks[index];
            backtrack(tasks, n, sessionTime, sessions, sessionCount, index + 1);
            sessions[i] -= tasks[index];
        }
    }
    
    // Try new session
    if (sessionCount < minSessions) {
        sessions[sessionCount] = tasks[index];
        backtrack(tasks, n, sessionTime, sessions, sessionCount + 1, index + 1);
    }
}

int solution(int* tasks, int n, int sessionTime) {
    qsort(tasks, n, sizeof(int), compare);
    minSessions = n;
    int* sessions = malloc(n * sizeof(int));
    backtrack(tasks, n, sessionTime, sessions, 0, 0);
    free(sessions);
    return minSessions;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int tasks[20];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        tasks[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int sessionTime;
    scanf("%d", &sessionTime);
    
    printf("%d\n", solution(tasks, n, sessionTime));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k^n)

For each of n tasks, we try k possible sessions, leading to exponential combinations

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth of n plus array to track session usage

⚠ Quadratic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Minimum Number of Work Sessions to Finish the Tasks - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Backtracking (Try All Combinations) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler