Free Dynamic programming lessonsDynamic programming · Stage 10 · Bitmask · Step 4

Keep a pair, and smaller is better

When the best answer for a set is two numbers that matter in order, pack them together and compare them as one. About 16 minutes.

Pack tasks into sessions

You have a list of tasks, each needing some hours, and work in sessions of a fixed length. A task can't be split across sessions, but you can do the tasks in any order. What is the fewest sessions that get everything done?

It is like packing boxes into as few delivery vans as possible. Two things matter about any plan so far: how many sessions you have started, and how many hours the latest one has used.

Two numbers: sessions so far, and hours used in the latest one.

One best pair for each set of tasks

For every set of tasks that are done, keep the best pair. A pair with fewer sessions is better. With the same number of sessions, fewer hours used in the latest one is better, because it leaves more room. Pack the pair into one number, sessions times 1,024 plus hours used, and then a smaller number really is a better pair.

Add a task to a set: if it fits in the latest session, add its hours. If not, start a new session with only that task. The answer is the session count for the set of every task.

Fits? add the hours to the latest session.

Doesn't fit? start a new session with that task.

In code

best = [INF] * (1 << n)
best[0] = 0

Tasks of 4, 2, 5, 3, 1 hours · sessions are 7 hours long

task

sessions: 1
hours used: 0

Start with nothing done: one session is open, and no hours are used.

Move 1 of 6

Quick check

Sessions are 8 hours long. The latest session has 6 hours used, and you add a 3-hour task. What happens?

AA new session starts, with 3 hours used
BThe latest session now has 9 hours used
CThe task is skipped

Show the answer

A new session starts, with 3 hours used. 6 + 3 = 9 is more than 8, so the task can't join the latest session.

Your problem

Fewest work sessions

You have a list of tasks, where tasks[i] is the hours task i takes, and you work in sessions that are each sessionTime hours long. A task must be finished within one session, but you may do the tasks in any order. Every task takes at most sessionTime hours. Return the smallest number of sessions needed to finish all the tasks.

Example

tasks = [3, 1, 3, 1, 1], sessionTime = 8 → 2

1 ≤ tasks ≤ 14 · 1 ≤ tasks[i] ≤ sessionTime ≤ 100

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.