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;
}
}
```