Deadline Scheduling Algorithm

HardPython

Problem

A Thales TopSky mission-planning component has a set of available tasks. Each task requires exclusive processor time, has a completion deadline, and provides value only if completed by that deadline. Tasks are non-preemptive, all are available at time 0, and at most one task can run at a time.

Return the IDs of a subset of tasks that maximizes total value. The returned IDs must be in a valid execution order. If multiple optimal schedules exist, any one is acceptable.

Formal Specification

Implement schedule_tasks(tasks), where tasks is a list of dictionaries. Each dictionary contains:

id: a unique string
duration: a positive integer
deadline: a positive integer
value: a non-negative integer

Return a list of task IDs. A selected task is valid only when its cumulative completion time is at most its deadline. Tasks that cannot be completed by their deadlines may be omitted.

Constraints

1 <= len(tasks) <= 100
1 <= tasks[i]["duration"] <= 20,000
1 <= tasks[i]["deadline"] <= 20,000
0 <= tasks[i]["value"] <= 10^6
Task IDs are unique strings
All tasks are available at time 0

Function Signature

def schedule_tasks(tasks):

Return the IDs of a subset of tasks that maximizes total value. The returned IDs must be in a valid execution order. If multiple optimal schedules exist, any one is acceptable.

Formal Specification

Implement schedule_tasks(tasks), where tasks is a list of dictionaries. Each dictionary contains:

id: a unique string
duration: a positive integer
deadline: a positive integer
value: a non-negative integer

Return a list of task IDs. A selected task is valid only when its cumulative completion time is at most its deadline. Tasks that cannot be completed by their deadlines may be omitted.