Overview

This problem involves constructing a bipartite graph between time slots and part-time worker candidates, and finding the maximum matching to determine the maximum number of hours staff can be assigned.

Analysis

Each time slot can have only one staff member assigned, and each staff member can be assigned to at most one time slot. This is a classic “bipartite matching” problem.

For example, if time slot 1 can be covered by candidates 1 and 2, and time slot 2 can be covered by candidates 2 and 3, the result changes depending on which time slot candidate 2 is assigned to. A greedy assignment may not yield the optimal solution, so an efficient algorithm is needed.

For such problems, a “maximum bipartite matching” algorithm (specifically Hopcroft-Karp or DFS-based augmenting path method) is effective for finding the maximum number of staff that can be properly assigned across all time slots.

Algorithm

This problem can be solved as a maximum bipartite matching problem on a bipartite graph where one set of vertices represents time slots and the other represents part-time worker candidates.

Specifically, it works as follows: 1. Construct a bipartite graph by adding edges from each time slot to the candidates who can work during that time slot. 2. For each time slot, if there is an unassigned candidate available, assign them. 3. If a candidate is already assigned, recursively adjust the assignment by searching for an alternative candidate from the time slot that candidate is currently assigned to (searching for an augmenting path). 4. Perform the above process for all time slots and count the number of successful matchings.

In the code, the dfs function is used to search for an augmenting path starting from a given time slot.

For example, if time slot A → candidate X is already matched, by finding a different candidate Y from time slot B (where X is currently assigned) and reassigning, it becomes possible to assign X to A.

Complexity

• Time complexity: \(O(N \cdot M \cdot N) = O(N^2 M)\) (augmenting path search via DFS is performed at most \(N\) times, traversing each edge)
• Space complexity: \(O(N + M + \sum K_i)\) (storing the adjacency list of the graph and matching information)

※In practice, using the Hopcroft-Karp algorithm can improve this to \(O(E \sqrt{V})\), but since the constraints are small, the DFS-based approach is sufficiently fast.

Implementation Notes

• Note that when constructing the graph, the input is read as 1-indexed.

• Having both match_worker_to_slot and match_slot_to_worker makes bidirectional lookups easy.

• A visited flag is used within the DFS to prevent infinite loops.

• In the input parsing section, all data is read at once for faster processing.

  Source Code

from collections import defaultdict

def max_bipartite_matching(N, M, candidates):
    # Build graph: time slot -> list of available workers
    graph = candidates
    
    # match[u] = v means worker u is assigned to time slot v (1-based)
    # -1 means unassigned
    match_worker_to_slot = [-1] * (M + 1)  # 1-based indexing for workers
    match_slot_to_worker = [-1] * (N + 1)   # 1-based indexing for slots
    
    def dfs(slot, visited):
        for worker in graph[slot]:
            if visited[worker]:
                continue
            visited[worker] = True
            
            # If the worker is free or we can find an alternative assignment
            if match_worker_to_slot[worker] == -1 or dfs(match_worker_to_slot[worker], visited):
                match_worker_to_slot[worker] = slot
                match_slot_to_worker[slot] = worker
                return True
        return False

    result = 0
    for slot in range(1, N + 1):
        visited = [False] * (M + 1)
        if dfs(slot, visited):
            result += 1
            
    return result

# Read input
import sys
input = sys.stdin.read
data = input().split()

idx = 0
N = int(data[idx])
idx += 1
M = int(data[idx])
idx += 1

candidates = [[] for _ in range(N + 1)]
for i in range(1, N + 1):
    K = int(data[idx])
    idx += 1
    for _ in range(K):
        c = int(data[idx])
        idx += 1
        candidates[i].append(c)

print(max_bipartite_matching(N, M, candidates))

This editorial was generated by qwen3-coder-480b.