1076. Two-Choice Planner
A planner must decide, for each of n tasks numbered 0 to n-1, whether to run it or skip it. Every rule names two options and demands that at least one of them is true. An option is a number x in the range 0 to 2n-1: task x / 2 (integer division) is the one it talks about, and the option is “run it” when x is even and “skip it” when x is odd.
Each entry clauses[i] = [a, b] is one rule. The two options of a rule may be equal, or may contradict each other (for example 0 and 1, which together are always satisfied). Return true if the tasks can be assigned run/skip so that every rule holds, otherwise false.
Example 1
- Input:
- n = 3, clauses = [[0,2],[1,4],[3,5]]
- Output:
- true
- Explanation:
Run tasks 0 and 2 and skip task 1: “run 0 or run 1”, “skip 0 or run 2” and “skip 1 or skip 2” all hold.
Example 2
- Input:
- n = 2, clauses = [[0,2],[0,3],[1,2],[1,3]]
- Output:
- false
- Explanation:
The four rules together forbid every one of the four ways to treat tasks 0 and 1, so no plan exists.
Example 3
- Input:
- n = 2, clauses = [[1,1],[0,3]]
- Output:
- true
- Explanation:
The first rule forces task 0 to be skipped; then the second rule needs task 1 to be skipped as well, which is allowed.
Constraints
1 ≤ n ≤ 3 * 104
0 ≤ clauses.length ≤ 6 * 104
clauses[i].length == 2
0 ≤ clauses[i][j] < 2 * n
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n + m)
- Space
- O(n + m)