Minimum Number of Work Sessions to Finish the Tasks

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

Understanding the Visualization

Input Tasks

Array of task durations and maximum session time

Group Optimally

Find best way to group tasks without exceeding session limits

Count Sessions

Return minimum number of sessions required

Key Takeaway

🎯 Key Insight: This is essentially a bin packing problem where we minimize the number of bins (sessions) needed to pack all items (tasks) with capacity constraints.

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

Approach	Time	Space	Notes
✓ Backtracking (Try All Combinations)	O(k^n)	O(n)	Try all possible ways to assign tasks to sessions
Dynamic Programming with Bitmasks	O(3^n)	O(2^n)	Use bitmasks to represent task subsets and find optimal partitioning

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

⚡ Linearithmic 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Backtracking (Try All Combinations) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler