Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1986.html

1986. Minimum Number of Work Sessions to Finish the Tasks

Level

Medium

Description

There are n tasks assigned to you. The task times are represented as an integer array tasks of length n, where the i-th 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

Solution

Use dynamic programming. For each work session, complete as many tasks as possible to make the total time closest to sessionTime, and complete the tasks with longer times first. Repeat the process until all tasks are finished.

  • class Solution {
    public int minSessions(int[] tasks, int sessionTime) {
        Arrays.sort(tasks);
        int total = 0;
        int length = tasks.length;
        for (int i = 0; i < length; i++)
            total += tasks[i];
        int maxIndex = length - 1;
        int sessions = 0;
        while (total > 0) {
            int maxTask = tasks[maxIndex];
            tasks[maxIndex] = 0;
            total -= maxTask;
            int maxTime = getMaxTime(tasks, sessionTime - maxTask);
            total -= maxTime;
            sessions++;
            while (maxIndex >= 0 && tasks[maxIndex] == 0)
                maxIndex--;
        }
        return sessions;
    }

    public int getMaxTime(int[] tasks, int sessionTime) {
        int length = tasks.length;
        int[][] dp = new int[length + 1][sessionTime + 1];
        for (int i = 0; i < length; i++) {
            int task = tasks[i];
            for (int j = 0; j <= sessionTime; j++) {
                dp[i + 1][j] = dp[i][j];
                if (j >= task)
                    dp[i + 1][j] = Math.max(dp[i + 1][j], dp[i][j - task] + task);
            }
        }
        int maxTime = dp[length][sessionTime];
        int temp = maxTime;
        boolean[] removed = new boolean[length];
        for (int i = length; i > 0; i--) {
            if (temp >= tasks[i - 1] && dp[i][temp] == dp[i - 1][temp - tasks[i - 1]] + tasks[i - 1]) {
                temp -= tasks[i - 1];
                removed[i - 1] = true;
            }
        }
        for (int i = 0; i < length; i++) {
            if (removed[i])
                tasks[i] = 0;
        }
        return maxTime;
    }
}

  • // OJ: https://leetcode.com/problems/minimum-number-of-work-sessions-to-finish-the-tasks/
// Time: O(3^N)
// Space: O(2^N)
class Solution {
    int m[16385] = {};
    bool valid[16385] = {};
    int dp(vector<int> &A, int mask, int total) {
        if (mask == 0) return 0;
        if (m[mask] != -1) return m[mask];
        int ans = INT_MAX;
        for (int ms = mask; ms; ms = (ms - 1) & mask) {
            if (!valid[ms]) continue;
            ans = min(ans, 1 + dp(A, mask & ~ms, total));
        }
        return m[mask] = ans;
    }
public:
    int minSessions(vector<int>& A, int total) {
        memset(m, -1, sizeof(m));
        for (int mask = 1; mask < (1 << A.size()); ++mask) {
            int sum = 0;
            for (int i = 0; i < A.size(); ++i) {
                if (mask >> i & 1) sum += A[i];
            }
            valid[mask] = sum <= total;
        }
        return dp(A, (1 << A.size()) - 1, total);
    }
};

  • # 1986. Minimum Number of Work Sessions to Finish the Tasks
# https://leetcode.com/problems/minimum-number-of-work-sessions-to-finish-the-tasks/

class Solution:
    def minSessions(self, tasks: List[int], sessionTime: int) -> int:
        n = len(tasks)
        
        @cache
        def go(mask, curr, session):
            if mask == 0: return session
            
            res = float('inf')
            
            for i in range(n):
                if mask & (1 << i):
                    if curr + tasks[i] <= sessionTime:
                        res = min(res, go(mask ^ (1 << i), curr + tasks[i], session))
                    else:
                        res = min(res, go(mask ^ (1 << i), tasks[i], session + 1))
            
            return res
        
        return go((1 << n) - 1, 0, 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]
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

  • 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];
}

All Problems

All Solutions