258. Minimum Time Task Scheduling with Constraints

Minimum Time Task Scheduling with Constraints

You are given a list of task types, a list of memory required by each task, and a server memory limit. Each task takes exactly 1 unit of time to complete.

In one unit of time, multiple tasks can run together if they satisfy both constraints: at most 2 tasks of the same type can run in parallel, and the total memory of all running tasks must not exceed the server memory limit.

Return the minimum time required to execute all tasks.

Method Signature

int minimumExecutionTime(List<String> type, List<Integer> memory, int serverMemoryLimit)

type contains the type of each task.
memory contains the memory required by each task.
type.get(i) and memory.get(i) describe the same task.
serverMemoryLimit is the maximum total memory allowed in one time unit.
The method returns the minimum number of time units needed to finish all tasks.

Scheduling Rules

Each task must be executed exactly once.
Each task takes exactly 1 unit of time.
During one time unit, the total memory of selected tasks must be at most serverMemoryLimit.
During one time unit, at most 2 tasks with the same type can run together.
A valid schedule may choose any non-empty subset of remaining tasks for each time unit until all tasks are completed.
If multiple optimal schedules exist, only the minimum time is returned, so the output is deterministic.

Constraints

1 ≤ type.size() ≤ 20
memory.size() = type.size()
1 ≤ type.get(i).length() ≤ 50
1 ≤ memory.get(i) ≤ serverMemoryLimit
1 ≤ serverMemoryLimit ≤ 1,000,000,000
type and memory are never null.
No value inside type is null or empty.
All input values are valid.

Examples

Example 1

minimumExecutionTime(type = ["A", "A", "B", "C"], memory = [2, 3, 2, 1], serverMemoryLimit = 5)

Output: 2

Explanation: One optimal schedule is [A(3), B(2)] in the first time unit and [A(2), C(1)] in the second time unit.

Example 2

minimumExecutionTime(type = ["A", "A", "A", "A"], memory = [1, 1, 1, 1], serverMemoryLimit = 10)

Output: 2

Explanation: Even though memory allows all tasks together, only 2 tasks of type A can run in parallel, so at least 2 time units are needed.

Example 3

minimumExecutionTime(type = ["A", "B", "C"], memory = [4, 4, 4], serverMemoryLimit = 5)

Output: 3

Explanation: No two tasks can run together because any pair exceeds the memory limit.

Example 4

minimumExecutionTime(type = ["A", "A", "B", "B", "C"], memory = [2, 2, 3, 1, 2], serverMemoryLimit = 5)

Output: 2

Explanation: One optimal schedule is [A(2), A(2), B(1)] and [B(3), C(2)].