Frontend School

Dependency-Aware Delivery Sequencing with Penalty Minimization

DSA
hard

Dependency-Aware Delivery Sequencing with Penalty Minimization

Hard
Topological Sort
Graph
Scheduling
Greedy
Priority Queue

Overview

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.

What you need to do / Task

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:

  1. Constructs a valid task sequence: The sequence must respect all given dependencies. If task u depends on task v, then v must appear before u in the sequence.
  2. Minimizes total penalty: Among all valid sequences, return one that results in the minimum possible total penalty. The penalty for a task is applied if its completion time exceeds its deadline.
  3. Handles cyclic dependencies: If a cycle exists in the dependencies, no valid sequence can be formed. In this case, the function should return an empty array [].

Input & output

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:

  • An array of numbers representing the task IDs in their optimal execution sequence. If multiple sequences yield the same minimum penalty, any one is acceptable.
  • An empty array [] if a cyclic dependency is detected, making a valid sequence impossible.

Clarifications

  • Tasks are 0-indexed, from 0 to n-1.
  • The total time elapsed for a sequence is the sum of 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.
  • A task i incurs penalty_i if completionTime_i > deadline_i. Penalties are additive; the total penalty is the sum of penalties for all late tasks.
  • If a task has no dependencies, it can be started as soon as it's ready (i.e., at time 0 if it's an initial task).

Examples

1

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]:

  • Task 0: completes at 5. (5 <= 8) -> Penalty 0.
  • Task 2: completes at 5+4=9. (9 <= 9) -> Penalty 0.
  • Task 1: completes at 9+3=12. (12 > 10) -> Penalty 50. Total penalty = 50. Any other valid sequence yields a higher penalty (e.g., [0,1,2] results in penalty 200).
2

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]:

  • Task 0: completes at 5. (5 <= 10) -> Penalty 0.
  • Task 1: completes at 5+5=10. (10 <= 10) -> Penalty 0.
  • Task 2: completes at 10+10=20. (20 > 18) -> Penalty 50.
  • Task 3: completes at 20+2=22. (22 <= 25) -> Penalty 0. Total penalty = 50. If [1,0,2,3] was chosen (by prioritizing Task 1 first due to some other tie-breaking), total penalty would also be 50.
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

Constraints & assumptions

  • 1 <= n <= 10^4
  • 0 <= dependencies.length <= n * (n - 1) / 2
  • 0 <= 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.
  • All input values are integers.

Out of scope

  • Parallel processing of tasks. All tasks must be executed sequentially on a single logical resource.
  • Resource constraints other than task dependencies (e.g., specific workers, machine availability).
  • Dynamic updates to dependencies or task information during execution.

What interviewers evaluate

  • Correctness of Topological Sort: Ability to correctly build a graph, compute in-degrees, and handle cyclic dependencies.
  • Effective Greedy Strategy: Designing and implementing a robust greedy approach using a priority queue to select the next task from available (zero in-degree) tasks to minimize total penalty.
  • Accurate Penalty Calculation: Correctly tracking current time and calculating penalties for late tasks.
  • Time and Space Complexity: Analysis of the solution's efficiency, aiming for an optimal O(V + E log V) or O(V + E) time complexity, where V is n and E is dependencies.length.

Loading editor...