Optimal Task Scheduling with Dependencies and Deadlines

This challenge explores the problem of scheduling tasks with dependencies and deadlines to maximize the number of completed tasks. Imagine you're managing a project with multiple tasks, each requiring a certain amount of time and having a deadline. Some tasks depend on others, and you need to find a schedule that completes as many tasks as possible before their deadlines, respecting the dependencies.

Problem Description

You are given a list of tasks, where each task is represented by a tuple: (task_id, duration, deadline, dependencies). task_id is a unique identifier for the task (an integer). duration is the time required to complete the task (an integer). deadline is the time by which the task must be completed (an integer). dependencies is a list of task_ids that must be completed before this task can start.

Your goal is to determine the maximum number of tasks that can be completed within their deadlines, respecting the dependencies. You must find a schedule that prioritizes tasks effectively. A task is considered "completed" if it starts and finishes before its deadline. Tasks can be started at any time, as long as their dependencies are met. You are not required to find the exact schedule, only the maximum number of completable tasks.

Examples

Example 1:

Input: [(1, 2, 5, []), (2, 3, 7, [1]), (3, 1, 4, [2])]
Output: 3
Explanation: We can complete task 1 (duration 2, deadline 5), then task 2 (duration 3, deadline 7, depends on 1), and finally task 3 (duration 1, deadline 4, depends on 2). All tasks are completed within their deadlines.

Example 2:

Input: [(1, 2, 4, []), (2, 3, 5, [1]), (3, 4, 6, [2])]
Output: 2
Explanation: We can complete task 1 (duration 2, deadline 4), then task 2 (duration 3, deadline 5, depends on 1). Task 3 (duration 4, deadline 6, depends on 2) cannot be completed within its deadline if we start it after completing task 2.

Example 3:

Input: [(1, 5, 8, []), (2, 3, 6, [1]), (3, 2, 7, [1]), (4, 4, 9, [2, 3])]
Output: 3
Explanation: We can complete task 1 (duration 5, deadline 8), then task 3 (duration 2, deadline 7, depends on 1), then task 2 (duration 3, deadline 6, depends on 1). Task 4 (duration 4, deadline 9, depends on 2 and 3) cannot be completed within its deadline.

Constraints

• The number of tasks will be between 1 and 1000.
• The duration of each task will be between 1 and 100.
• The deadline of each task will be between 1 and 10000.
• The number of dependencies for each task will be between 0 and 100.
• Dependencies will always be valid task IDs present in the input list.
• The algorithm should ideally run in a reasonable time (e.g., O(n log n) or better, where n is the number of tasks). A brute-force approach is unlikely to pass all test cases.

Notes

• Consider sorting tasks based on their deadlines. This is often a good heuristic for scheduling problems.
• Topological sorting can be helpful for managing dependencies.
• Dynamic programming or greedy approaches might be suitable, but carefully consider the constraints and edge cases.
• The problem asks for the maximum number of tasks that can be completed, not the specific schedule itself.
• Be mindful of how dependencies affect the feasibility of completing a task within its deadline.
• Think about how to efficiently track which tasks are ready to be scheduled (i.e., all dependencies are met).

Pseudocode:

function max_tasks_scheduled(tasks):
  # Sort tasks by deadline in ascending order
  sorted_tasks = sort tasks by deadline

  # Initialize variables
  completed_tasks = 0
  current_time = 0
  ready_tasks = []

  # Create a dictionary to track dependencies
  dependency_counts = {}
  for task_id, _, _, dependencies in tasks:
    dependency_counts[task_id] = len(dependencies)

  # Add tasks with no dependencies to the ready_tasks list
  for task_id, _, _, dependencies in tasks:
    if dependency_counts[task_id] == 0:
      ready_tasks.append((task_id, tasks[task_id - 1][1], tasks[task_id - 1][2])) # (task_id, duration, deadline)

  while ready_tasks:
    # Sort ready tasks by deadline
    ready_tasks.sort(key=lambda x: x[2])

    # Select the task with the earliest deadline
    task_id, duration, deadline = ready_tasks.pop(0)

    # Check if the task can be completed within its deadline
    if current_time + duration <= deadline:
      completed_tasks += 1
      current_time += duration

      # Update dependency counts for dependent tasks
      for task_id_dependent, _, _, dependencies in tasks:
        if task_id in dependencies:
          dependency_counts[task_id_dependent] -= 1
          if dependency_counts[task_id_dependent] == 0:
            ready_tasks.append((task_id_dependent, tasks[task_id_dependent - 1][1], tasks[task_id_dependent - 1][2]))

  return completed_tasks