Check a Proposed Schedule

EasyGraphs

Problem

There are n jobs numbered 0 to n - 1. Each entry [a, b] of deps means job a must run before job b.

A colleague proposes running the jobs in the sequence order. Return true if order lists every job exactly once and respects every dependency, and false otherwise.

Example 1

Input:
n = 4, deps = [[0, 1], [0, 2], [1, 3], [2, 3]], order = [0, 2, 1, 3]
Output:
true

0 comes before 1 and 2, and both come before 3.

Example 2

Input:
n = 4, deps = [[0, 1], [0, 2], [1, 3], [2, 3]], order = [0, 3, 1, 2]
Output:
false

Job 3 runs before job 1, breaking [1, 3].

Example 3

Input:
n = 3, deps = [[0, 1]], order = [0, 1]
Output:
false

Job 2 is missing.

Constraints

  • 1 ≤ n ≤ 10^5
  • 0 ≤ deps.length ≤ 2·10^5
  • 0 ≤ a, b < n, a ≠ b
  • 0 ≤ order.length ≤ 2·10^5, 0 ≤ order[i] ≤ 10^9

Hint

Show the first hint

There are two separate things to check: that order is a permutation, and that dependencies are respected.

Walkthrough

How to approach it

01Clarify before coding

  • Must order contain every job? Yes, exactly once; missing, repeated or unknown jobs make it invalid.
  • Are there cycles in deps? Possibly; then no order can be valid, and the per-edge check rejects every proposal automatically.
  • Can order be longer than n? Yes, and then it cannot be a permutation.

02Brute force

For every dependency [a, b], search order linearly for a and for b and compare where they were found.

Cost: O(m·n): two linear searches per dependency, up to 4·10^10 steps.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.