Part of Advent of Code Golf 2021 event. See the linked meta post for details.

The story continues from AoC2018 Day 7, Part 2.

Why I'm pxeger, not Bubbler

As soon as you and a few Elves successfully assemble the Sleigh kit, you spot another set of the same kit not so far away. But you noticed that the last Elf is slacking quite a lot but you had to work from start to end without having any free time at all.

In an attempt to fix this, you decide to take a specific number of Elves to maximize your free time.

This time, you and the Elves learned how to assemble it, so each job numbered n exactly takes n seconds to complete (instead of n + 60 seconds). And, to simplify things, the manual is given simply as a list of pairs of job numbers, each pair (x, y) meaning "job x should be completed before job y can begin". The smallest-numbered worker available (you being number 1 and the Elves being number 2, 3, ...) takes the next available job, smallest number first.

Given the example manual

[(3, 1), (3, 6), (1, 2), (1, 4), (2, 5), (4, 5), (6, 5)]

the visual order of the jobs is as follows:

  -->1--->2--
 /    \      \
3      -->4----->5
 \           /
  ---->6-----

If you take 0, 1, or 2 Elves with you (being 1, 2, 3 workers in total), the following will happen respectively:

1 worker:
you   | 333122444466666655555

2 workers:
you   | 333122444455555
elf 1 |    666666

3 workers:
you   | 333122   55555
elf 1 |    666666
elf 2 |     4444

So you get 3 seconds of rest when there are 3 workers, and no time to rest with fewer. Since there is no opportunity to do 4 jobs in parallel, the 3-worker case is the best for you. If multiple choices give the same amount of time to rest, choose the fewest number of workers.

Input: A description of the manual. Assume every job to be done appears in the manual, and the job numbers are consecutive from 1.

Output: The optimal total number of workers.

Standard code-golf rules apply. The shortest code in bytes wins.

Test cases

[(2, 1), (3, 2)] -> 1
[(3, 1), (3, 6), (1, 2), (1, 4), (2, 5), (4, 5), (6, 5)] -> 3
[(2, 3), (2, 5), (8, 6), (8, 4), (3, 7), (6, 7), (5, 1), (4, 1)] -> 3
+-2-+-3--+--7-+
|   +-5--|+   |
|        ||   |
+-8-+-6--+|   |
    +-4---+-1-+
1 worker:
2-3-5-8-4-1-6-7
2 worker:
22333555556666667777777
8888888844441
3 worker: (same as 4 worker; no way to parallelize [3, 4, 5, 6])
22333...44441.7777777
88888888666666
  55555