All problems

Critical Steps

Medium · topological sort

A project is made of n steps numbered 0 to n - 1. Step i takes durations[i] minutes. The list prerequisites holds pairs [a, b], meaning step a must be completely finished before step b can start.

Any number of steps can be worked on at the same time. Every step starts the moment all of its prerequisites are finished (a step with no prerequisites starts at minute 0). The project is finished when every step is finished.

A step is critical if making it take one minute longer would make the whole project finish later. Return the number of critical steps.

The prerequisites never form a cycle, and no pair appears twice.

Examples

Example 1

Input: durations = [3, 2, 4, 1], prerequisites = [[0, 1], [0, 2], [1, 3], [2, 3]]

Output: 3

Step 0 leads to step 3 through step 1 (3 + 2 + 1 = 6 minutes) or through step 2 (3 + 4 + 1 = 8 minutes). The project takes 8 minutes, and steps 0, 2 and 3 are on that long route. Making step 1 a minute longer still finishes in 8 minutes.

Example 2

Input: durations = [5, 5], prerequisites = []

Output: 2

The two steps run side by side and both end at minute 5. Delaying either one pushes the end of the project to minute 6.

Example 3

Input: durations = [2, 1, 1], prerequisites = [[0, 2], [1, 2]]

Output: 2

Step 2 waits for step 0 (finished at minute 2) and step 1 (finished at minute 1). Steps 0 and 2 form the long route.

Constraints