Task Scheduler with Dependencies

Graph Scheduling Algorithms

You are given a set of tasks that need to be executed on a single processor. Each task is represented as a JSON object with the following keys:

  • id: A unique string identifier for the task.
  • time: An integer representing the amount of time the task takes to complete.
  • deadline: An integer indicating the time by which the task must be completed. (Assume time starts at 0.)
  • prereq: A list of task ids that must be completed before this task can start.

Example of a task:

{
  "id": "task1",
  "time": 3,
  "deadline": 10,
  "prereq": []
}

Your task:

  1. Write a function that takes a list of such tasks as input.
  2. Determine if there exists an ordering of task executions such that:
    • All prerequisites for each task are met before it is scheduled.
    • Each task is completed by its deadline (i.e., the sum of execution times up to and including that task is less than or equal to its deadline).
  3. If such a schedule exists, return an ordering (as a list of task ids) that satisfies these requirements.
  4. If it is impossible to schedule the tasks in a valid order, the function should indicate that scheduling is not possible (for example, by returning an empty list or a specific message).

Assume that the tasks are executed sequentially and there is no idle time between tasks. Consider edge cases such as cyclic dependencies and scenarios where deadlines cannot be met even if the dependencies are satisfied.

Design your solution to be efficient and well-organized.