Assign Two Shifts
MediumGraphs
Problem
A clinic schedules n nurses numbered 0 to n - 1 into a day shift (0) or a night shift (1). Each entry [a, b] of conflicts means nurses a and b must work different shifts.
Return an array shift of length n that satisfies every conflict. Among all valid assignments, return the lexicographically smallest one. If no valid assignment exists, return an empty array.
Example 1
- Input:
- n = 4, conflicts = [[0, 1], [1, 2], [2, 3]]
- Output:
- [0, 1, 0, 1]
[1, 0, 1, 0] is also valid, but it is larger at position 0.
Example 2
- Input:
- n = 3, conflicts = [[0, 1], [1, 2], [0, 2]]
- Output:
- []
Three nurses who all conflict cannot fit into two shifts.
Example 3
- Input:
- n = 5, conflicts = [[3, 1], [4, 2]]
- Output:
- [0, 0, 0, 1, 1]
Nurse 0 is free; nurses 1 and 2 take day, so 3 and 4 take night.
Constraints
- 1 ≤ n ≤ 10^4
- 0 ≤ conflicts.length ≤ 2·10^4
- 0 ≤ a, b < n, a ≠ b
Hint
Show the first hint
Within one connected group of conflicts, how many valid assignments are there?
Walkthrough
How to approach it
01Clarify before coding
- What is lexicographic order here? Compare shift arrays position by position; the first difference decides.
- What about nurses with no conflicts? They are free, so they get 0.
- If impossible, what to return? An empty array.
02Brute force
Enumerate all 2^n assignments in increasing order and return the first that satisfies every conflict.
Cost: O(2^n · m): infeasible beyond n ≈ 25.
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.
This problem is part of Pro.