Group 7 — Optimization and Planning

This group focuses on optimization problems where several valid solutions may exist, but the goal is to find the best one according to a defined objective.

Earlier algorithm groups mainly focus on:

• searching
• filtering
• grouping
• combinations
• graph traversal
• validation
• state transitions
• scheduling simulation

This group introduces a different question:

Out of all valid solutions, which one is best?

The tasks cover several common optimization patterns:

• selecting non-overlapping intervals
• selecting requests under capacity constraints
• assigning jobs to workers
• planning routes under capacity limits
• scheduling jobs with deadlines and penalties

The main challenge is not only producing a valid result.

The implementation must also evaluate competing solutions and select the one that optimizes the required metric.

Task 1 — Weighted Interval Scheduling

Given a list of jobs with:

start time
end time
value

select a set of non-overlapping jobs whose total value is maximal.

The task introduces:

• interval conflicts
• sorting by time
• compatibility relationships
• dynamic programming
• reconstruction of the selected solution

Task 2 — Multi-Resource Capacity Selection

Given a set of requests that consume several limited resources such as:

CPU
memory
storage

select the combination of requests that produces the maximum total value without exceeding capacity.

The task introduces:

• multidimensional capacity constraints
• subset optimization
• exact versus heuristic reasoning
• deterministic tie-breaking

Task 3 — Minimum Cost Assignment

Given a set of workers and jobs where each worker has a different cost for every job, assign jobs to workers so that:

each job is assigned exactly once
each worker receives at most one job

and total assignment cost is minimal.

The task introduces:

• assignment optimization
• cost matrices
• one-to-one constraints
• solution reconstruction

Task 4 — Capacity-Constrained Route Planning

Given delivery locations with demands and vehicles with limited capacity, create valid delivery routes.

The objective is to minimize:

total route cost

while satisfying all capacity constraints.

The task introduces:

• route planning
• capacity constraints
• multiple routes
• graph costs
• optimization under combinatorial growth

Task 5 — Deadline and Penalty Scheduling

Given jobs with:

duration
deadline
late penalty

schedule the jobs on a limited number of workers or machines.

The goal is to minimize total penalty caused by late jobs.

The task introduces:

• sequencing
• finite resources
• completion times
• deadlines
• penalty-based optimization
• deterministic scheduling

General Requirements

Solutions should validate input before processing.

Common invalid cases include:

negative duration
invalid interval
negative cost
negative capacity
request exceeding all available capacity
duplicate IDs
unknown references
invalid worker count
invalid route data

When multiple solutions have the same optimal objective value, the implementation must apply deterministic tie-breaking.

Unless a task defines a different rule, use:

lexicographical order of IDs

when equivalent solutions exist.

Algorithm Choice

The tasks are designed so that several approaches may be possible.

Depending on the input size, an implementation may use:

dynamic programming
backtracking
branch and bound
memoization
graph algorithms
exhaustive search for small inputs

The exercise should not use a library function that directly solves the complete optimization problem.

The objective is to implement the decision logic.

Result Reconstruction

For optimization tasks, returning only the optimal numeric value is not enough.

For example:

Maximum Value = 124

does not explain which jobs produced the result.

Solutions should return both:

objective value
selected solution

Examples:

selected job IDs
selected request IDs
worker-to-job assignments
vehicle routes
scheduled jobs

Goal

The goal of this group is to practice problems where correctness has two levels:

Is the solution valid?

Is the solution optimal?

A valid but non-optimal solution should not be considered correct when the task explicitly requires the best result.