Dependency-Aware Delivery Sequencing with Penalty Minimization
At Delhivery, optimizing the sequence of delivery tasks in a warehouse or hub is crucial for operational efficiency and meeting strict service level agreements (SLAs). Each task, such as sorting a package or loading a truck, has a specific processing time and must adhere to certain dependencies (e.g., package must be sorted before it can be loaded). Missing a task's deadline incurs a penalty. This problem challenges you to design an algorithm that determines an optimal sequence of tasks to minimize the total accumulated penalties, respecting all dependencies.
You are given a set of n delivery tasks. For each task, you know its processing time, a deadline, and a penalty incurred if the task is completed after its deadline. Additionally, a list of dependencies specifies which tasks must be completed before others.
Your goal is to implement a function findOptimalDeliverySequence that:
u depends on task v, then v must appear before u in the sequence.[].Function Signature:
function findOptimalDeliverySequence(n: number, dependencies: number[][], taskInfo: number[][]): number[]
Parameters:
n: An integer representing the total number of tasks, from 0 to n-1.dependencies: An array of pairs [u, v], where u and v are task IDs. This indicates that task u must be completed before task v (i.e., u is a prerequisite for v).taskInfo: An array of arrays, where taskInfo[i] contains [processingTime_i, deadline_i, penalty_i] for task i.
processingTime_i: The time required to complete task i.deadline_i: The deadline for task i. If task_i completes at time C_i and C_i > deadline_i, a penalty penalty_i is incurred.penalty_i: The penalty value for task i if it's completed late.Return Value:
numbers representing the task IDs in their optimal execution sequence. If multiple sequences yield the same minimum penalty, any one is acceptable.[] if a cyclic dependency is detected, making a valid sequence impossible.0 to n-1.processingTime for all tasks executed so far in that sequence. A task's completion time is the current total elapsed time immediately after its execution.i incurs penalty_i if completionTime_i > deadline_i. Penalties are additive; the total penalty is the sum of penalties for all late tasks.Examples
Example 1
Input:
n = 3, dependencies = [[0, 1], [0, 2]], taskInfo = [[5, 8, 100], [3, 10, 50], [4, 9, 200]]
Output:
[0,2,1]
Note:
Tasks: Task 0 (p=5, d=8, pen=100), Task 1 (p=3, d=10, pen=50), Task 2 (p=4, d=9, pen=200). Initial ready: Task 0. After Task 0 (completion time 5, no penalty), Tasks 1 and 2 are ready. Priority Queue (sorted by deadline ASC, then penalty DESC, then processingTime ASC, then ID ASC): Task 2 (d=9, pen=200) then Task 1 (d=10, pen=50). Sequence [0, 2, 1]:
Example 2
Input:
n = 4, dependencies = [[0, 2], [1, 2], [2, 3]], taskInfo = [[5, 10, 100], [5, 10, 100], [10, 18, 50], [2, 25, 200]]
Output:
[0,1,2,3]
Note:
Tasks: Task 0 (p=5, d=10, pen=100), Task 1 (p=5, d=10, pen=100), Task 2 (p=10, d=18, pen=50), Task 3 (p=2, d=25, pen=200). Initial ready: Tasks 0 and 1. Both have deadline 10 and penalty 100. Using the priority rule (deadline ASC, penalty DESC, processingTime ASC, ID ASC), Task 0 is chosen over Task 1 (due to smaller ID). Sequence [0, 1, 2, 3]:
Example 3
Input:
n = 2, dependencies = [[0, 1], [1, 0]], taskInfo = [[10, 20, 100], [5, 10, 50]]
Output:
[]
Note:
Tasks 0 and 1 have a cyclic dependency (0 must precede 1, and 1 must precede 0). No valid topological order exists, so an empty array is returned.
Constraints
1 <= n <= 10^40 <= dependencies.length <= n * (n - 1) / 20 <= u, v < n, u != v for all [u, v] in dependencies.1 <= processingTime_i <= 100 for all tasks.1 <= deadline_i <= 10^9 for all tasks.1 <= penalty_i <= 1000 for all tasks.O(V + E log V) or O(V + E) time complexity, where V is n and E is dependencies.length.Loading editor...