Is Graph Bipartite?
Real-world version: Two Shift Conflict SplitThe statement here is our own: the same inputs, outputs and technique.
A repair depot has workstations numbered 0 through n - 1. Two workstations that draw
from the same power rail cannot be serviced during the same shift. The clash list is given
as conflicts, where conflicts[u] holds every workstation that clashes with workstation
u.
Clashes are mutual: whenever v occurs in conflicts[u], u occurs in conflicts[v].
No workstation clashes with itself, and no workstation is listed twice inside one entry.
Some workstations may have an empty clash list, and the clashes may break the floor into
several groups with no link between them.
The depot runs exactly two shifts, morning and evening, and every workstation must be
booked into one of them. Return true when a booking exists that keeps each clashing pair
in different shifts, and false when no such booking exists.
Examples
Example 1
- Input
- conflicts = [[2,3],[3,4],[0],[0,1],[1]]
- Output
- true
Book workstations 0 and 1 in the morning and workstations 2, 3 and 4 in the evening. Each of the four listed clashes has its two ends in different shifts.
Example 2
- Input
- conflicts = [[1,2,4],[0,2],[0,1],[4],[0,3]]
- Output
- false
Every way of booking these five workstations into two shifts leaves at least one listed clash with both ends in the same shift.
Example 3
- Input
- conflicts = [[1],[0],[3,4],[2,4],[2,3]]
- Output
- false
No booking of all five workstations keeps every listed clash split across the two shifts.
Constraints
- conflicts.length == n
- 1 <= n <= 100
- 0 <= conflicts[u].length < n
- 0 <= conflicts[u][i] <= n - 1
- conflicts[u] does not contain u.
- All the values of conflicts[u] are unique.
- If conflicts[u] contains v, then conflicts[v] contains u.
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def can_split_shifts(conflicts: list[list[int]]) -> bool:public boolean canSplitShifts(int[][] conflicts)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 11 test cases: 11 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's