Overview

This is a matching optimization problem where we need to determine if all \(M\) part-time workers can be assigned to \(N\) business days, and if possible, find the maximum revenue.

Analysis

Key Observations

1. Worker skill constraints: Worker \(j\) can only be assigned to days where \(H_i \leq P_j\). In other words, workers with lower skill levels have fewer days they can be assigned to.

2. Applying greedy approach: When processing workers in ascending order of skill level, workers processed later can work on “days the previous workers could handle + additional days.” This makes the strategy of processing workers with fewer options first effective.

Problems with Naive Approach

Trying all combinations of workers and business days would require \(O(N \times M)\) time, or \(O(NM)\) or more with bipartite matching, which would result in TLE for \(N, M \leq 2 \times 10^5\).

Solution

We optimize using a greedy approach with sorting + priority queue (heap).

• Sort workers by skill level in ascending order
• Sort business days by required skill level in ascending order
• When processing each worker, sequentially add available days to the heap and select the day with maximum revenue

Algorithm

1. Preprocessing

   • Sort worker skill levels \(P\) in ascending order
   • Sort business days by required skill level \(H\) in ascending order

2. Greedy Assignment

   • Prepare a max-heap (to extract days with highest revenue first)
   • Process workers in ascending order of skill level:
     • Add days with required skill at most \(P_j\) (current worker’s skill) to the heap
     • Extract the day with maximum revenue from the heap and assign it
     • If the heap is empty, assignment is impossible (output -1)

3. Output Result

   • If all workers are successfully assigned, output the total revenue

Concrete Example

For \(P = [3, 5, 7]\) (sorted) and business days \((H, S) = [(2, 100), (4, 200), (6, 150)]\) (sorted by \(H\)):

• Worker 1 (skill 3): Days with \(H \leq 3\) → Add \((2, 100)\) to heap → Select revenue 100
• Worker 2 (skill 5): Days with \(H \leq 5\) → Add \((4, 200)\) → Select revenue 200
• Worker 3 (skill 7): Days with \(H \leq 7\) → Add \((6, 150)\) → Select revenue 150
• Total: \(100 + 200 + 150 = 450\)

Complexity

• Time complexity: \(O(N \log N + M \log M + (N + M) \log N)\)
  • Sorting: \(O(N \log N + M \log M)\)
  • Heap operations: Each day is added at most once and removed at most once, so \(O(N \log N)\)
  • Overall: \(O((N + M) \log N)\)
• Space complexity: \(O(N + M)\) (arrays for sorting and heap)

Implementation Notes

• Python’s heapq is a min-heap, so we add revenues as negative values to use it as a max-heap
• Use a while loop for adding business days, advancing the pointer day_idx to process each day only once
• If there are no available days for a worker (heap is empty), immediately output -1 and terminate

Source Code

import heapq
from collections import defaultdict

def solve():
    N, M = map(int, input().split())
    
    days = []
    for i in range(N):
        H, S = map(int, input().split())
        days.append((H, S))
    
    P = list(map(int, input().split()))
    
    # Sort workers by skill level (ascending)
    P.sort()
    
    # Sort business days by required skill level (ascending)
    # (H, S, original_index)
    sorted_days = sorted(enumerate(days), key=lambda x: x[1][0])
    
    # Greedy approach: Process workers in ascending order of skill level
    # For each worker, among the days they can handle,
    # select the unassigned day with maximum revenue
    
    # Use max-heap (Python has min-heap, so we use negative values)
    max_heap = []
    day_idx = 0
    total_profit = 0
    assigned_count = 0
    
    for skill in P:
        # Add days this worker can handle (H <= skill) to the heap
        while day_idx < N and sorted_days[day_idx][1][0] <= skill:
            orig_idx, (H, S) = sorted_days[day_idx]
            heapq.heappush(max_heap, -S)  # Negative for max-heap
            day_idx += 1
        
        # Select the day with maximum revenue from the heap
        if max_heap:
            total_profit += -heapq.heappop(max_heap)
            assigned_count += 1
        else:
            # No available day to assign this worker
            print(-1)
            return
    
    if assigned_count == M:
        print(total_profit)
    else:
        print(-1)

solve()

---

This editorial was generated by claude4.5opus.