Overview

There are \(N\) part-time workers and \(M\) tasks. The problem is to assign a part-time worker with sufficient skill level to each task and maximize the total satisfaction.

Analysis

In this problem, exactly one part-time worker must be assigned to each task. However, each worker can handle at most one task, and the worker’s skill level \(A_i\) must be at least the task’s required skill level \(D_j\) (i.e., \(A_i - D_j \geq 0\)).

Key Observations

• By processing tasks in decreasing order of required skill level, we can choose from a larger pool of candidates.
• For each task, it is optimal to select the worker with the highest skill level among those who meet the required skill level (greedy approach).
• However, simply always choosing “the person with the highest skill” may leave no available workers for later tasks.

Solution: Using a Priority Queue (Heap)

• For each task, select the worker with the highest skill level among those currently available to handle it.
• To reuse previously seen workers with high skill levels, we use a max heap.
• Since exhaustive search each time would be too slow, we efficiently process by adding candidates to the heap and extracting from it.

Concrete Example

Consider the following input:

N=3, M=2
A = [5, 3, 4]
D = [4, 3]

1. Sort in descending order:

   • A = [5, 4, 3]
   • D = [4, 3]

2. Process tasks in decreasing order of required skill (D=[4,3]):

   • D=4: Workers with A>=4 are [5,4] → add to heap → select the maximum, 5
   • D=3: Workers with A>=3 are the remaining 4 and 3 → select the maximum from the heap, 4

The resulting satisfaction is \((5-4)+(4-3)=2\)

Algorithm

1. Sort both the workers’ skill level list \(A\) and the tasks’ required skill level list \(D\) in descending order.
2. Process tasks in decreasing order of required skill.
3. For each task:
   • Among unused workers, add those whose skill level is at least the current task’s required skill level to the heap.
   • If the heap is empty, assignment is impossible, so output -1 and terminate.
   • Otherwise, extract the worker with the highest skill level from the heap and assign them to the task.
   • Add the satisfaction \(A_i - D_j\) from the extracted worker.
4. Once all tasks have been assigned, output the total satisfaction.

Complexity

• Time complexity: \(O(N \log N + M \log M + M \log N)\) (Sorting is dominant. Additionally, heap operations are performed \(M\) times, each taking \(O(\log N)\))
• Space complexity: \(O(N)\) (The heap stores at most \(N\) elements)

Implementation Notes

• Python’s heapq is a min heap, so to use it as a max heap, elements need to be negated.

• By sorting both workers and tasks in descending order, we can efficiently add only the necessary information to the heap.

• If no worker satisfying the condition exists for a given task, we can immediately return -1 for early termination.

  Source Code

import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    A = list(map(int, data[2:2+N]))
    D = list(map(int, data[2+N:2+N+M]))
    
    # スキル値と要求スキル値を降順にソート
    A.sort(reverse=True)
    D.sort(reverse=True)
    
    # 最大ヒープ（Pythonでは最小ヒープなので、符号反転して利用）
    heap = []
    total_satisfaction = 0
    a_index = 0
    
    for d in D:
        # 現在の業務の要求スキル値 d に対して、A_i >= d となる i を探す
        while a_index < N and A[a_index] >= d:
            heapq.heappush(heap, -A[a_index])  # 最大ヒープとして使うために符号反転
            a_index += 1
        
        # ヒープが空なら、この業務を誰にも割り当てられない
        if not heap:
            print(-1)
            return
        
        # 満足度が最大になるようなアルバイトを選ぶ（貪欲法）
        max_a = -heapq.heappop(heap)
        total_satisfaction += max_a - d
    
    print(total_satisfaction)

if __name__ == "__main__":
    main()

---

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