1986. Minimum Number of Work Sessions to Finish the Tasks

Description

There are n tasks assigned to you. The task times are represented as an integer array tasks of length n, where the ith task takes tasks[i] hours to finish. A work session is when you work for at most sessionTime consecutive hours and then take a break.

You should finish the given tasks in a way that satisfies the following conditions:

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

Given tasks and sessionTime, return the minimum number of work sessions needed to finish all the tasks following the conditions above.

The tests are generated such that sessionTime is greater than or equal to the maximum element in tasks[i].

 

Example 1:

Input: tasks = [1,2,3], sessionTime = 3
Output: 2
Explanation: You can finish the tasks in two work sessions.
- First work session: finish the first and the second tasks in 1 + 2 = 3 hours.
- Second work session: finish the third task in 3 hours.

Example 2:

Input: tasks = [3,1,3,1,1], sessionTime = 8
Output: 2
Explanation: You can finish the tasks in two work sessions.
- First work session: finish all the tasks except the last one in 3 + 1 + 3 + 1 = 8 hours.
- Second work session: finish the last task in 1 hour.

Example 3:

Input: tasks = [1,2,3,4,5], sessionTime = 15
Output: 1
Explanation: You can finish all the tasks in one work session.

 

Constraints:

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

Solutions

Solution 1: State Compression Dynamic Programming + Subset Enumeration

We note that \(n\) does not exceed \(14\), so we can consider using state compression dynamic programming to solve this problem.

We use a binary number \(i\) of length \(n\) to represent the current task state, where the \(j\)-th bit of \(i\) is \(1\) if and only if the \(j\)-th task is completed. We use \(f[i]\) to represent the minimum number of work sessions needed to complete all tasks with state \(i\).

We can enumerate all subsets \(j\) of \(i\), where each bit of the binary representation of \(j\) is a subset of the corresponding bit of the binary representation of \(i\), i.e., \(j \subseteq i\). If the tasks corresponding to \(j\) can be completed in one work session, then we can update \(f[i]\) using \(f[i \oplus j] + 1\), where \(i \oplus j\) represents the bitwise XOR of \(i\) and \(j\).

The final answer is \(f[2^n - 1]\).

The time complexity is \(O(n \times 3^n)\), and the space complexity is \(O(2^n)\). Here, \(n\) is the number of tasks.

Python3JavaC++GoTypeScript

class Solution:
    def minSessions(self, tasks: List[int], sessionTime: int) -> int:
        n = len(tasks)
        ok = [False] * (1 << n)
        for i in range(1, 1 << n):
            t = sum(tasks[j] for j in range(n) if i >> j & 1)
            ok[i] = t <= sessionTime
        f = [inf] * (1 << n)
        f[0] = 0
        for i in range(1, 1 << n):
            j = i
            while j:
                if ok[j]:
                    f[i] = min(f[i], f[i ^ j] + 1)
                j = (j - 1) & i
        return f[-1]

class Solution {
    public int minSessions(int[] tasks, int sessionTime) {
        int n = tasks.length;
        boolean[] ok = new boolean[1 << n];
        for (int i = 1; i < 1 << n; ++i) {
            int t = 0;
            for (int j = 0; j < n; ++j) {
                if ((i >> j & 1) == 1) {
                    t += tasks[j];
                }
            }
            ok[i] = t <= sessionTime;
        }
        int[] f = new int[1 << n];
        Arrays.fill(f, 1 << 30);
        f[0] = 0;
        for (int i = 1; i < 1 << n; ++i) {
            for (int j = i; j > 0; j = (j - 1) & i) {
                if (ok[j]) {
                    f[i] = Math.min(f[i], f[i ^ j] + 1);
                }
            }
        }
        return f[(1 << n) - 1];
    }
}

class Solution {
public:
    int minSessions(vector<int>& tasks, int sessionTime) {
        int n = tasks.size();
        bool ok[1 << n];
        memset(ok, false, sizeof(ok));
        for (int i = 1; i < 1 << n; ++i) {
            int t = 0;
            for (int j = 0; j < n; ++j) {
                if (i >> j & 1) {
                    t += tasks[j];
                }
            }
            ok[i] = t <= sessionTime;
        }
        int f[1 << n];
        memset(f, 0x3f, sizeof(f));
        f[0] = 0;
        for (int i = 1; i < 1 << n; ++i) {
            for (int j = i; j; j = (j - 1) & i) {
                if (ok[j]) {
                    f[i] = min(f[i], f[i ^ j] + 1);
                }
            }
        }
        return f[(1 << n) - 1];
    }
};

func minSessions(tasks []int, sessionTime int) int {
    n := len(tasks)
    ok := make([]bool, 1<<n)
    f := make([]int, 1<<n)
    for i := 1; i < 1<<n; i++ {
        t := 0
        f[i] = 1 << 30
        for j, x := range tasks {
            if i>>j&1 == 1 {
                t += x
            }
        }
        ok[i] = t <= sessionTime
    }
    for i := 1; i < 1<<n; i++ {
        for j := i; j > 0; j = (j - 1) & i {
            if ok[j] {
                f[i] = min(f[i], f[i^j]+1)
            }
        }
    }
    return f[1<<n-1]
}

function minSessions(tasks: number[], sessionTime: number): number {
    const n = tasks.length;
    const ok: boolean[] = new Array(1 << n).fill(false);
    for (let i = 1; i < 1 << n; ++i) {
        let t = 0;
        for (let j = 0; j < n; ++j) {
            if (((i >> j) & 1) === 1) {
                t += tasks[j];
            }
        }
        ok[i] = t <= sessionTime;
    }

    const f: number[] = new Array(1 << n).fill(1 << 30);
    f[0] = 0;
    for (let i = 1; i < 1 << n; ++i) {
        for (let j = i; j > 0; j = (j - 1) & i) {
            if (ok[j]) {
                f[i] = Math.min(f[i], f[i ^ j] + 1);
            }
        }
    }
    return f[(1 << n) - 1];
}

Comments