Overview

Given \(N\) staff members and \(M\) jobs, where each job has assignment conditions (staff efficiency must be at least a certain value), find the maximum number of jobs that can be completed through one-to-one matching.

Analysis

Problem Reformulation

The condition for staff \(i\) to handle job \(j\) is \(D_j \leq V_i \times T_j\). Rearranging this: $\(V_i \geq \frac{D_j}{T_j}\)$

In other words, each job \(j\) has a “minimum required efficiency” \(\lceil D_j / T_j \rceil\), and only staff with efficiency at or above this value can handle it.

Issues with Naive Approach

Trying all pairs of jobs and staff would be \(O(NM)\), which with \(N, M \leq 2 \times 10^5\) requires up to \(4 \times 10^{10}\) computations, resulting in TLE.

Solution Using Greedy Algorithm

This problem can be solved using the classic greedy approach for “job assignment.”

Key Observation: Jobs with higher minimum required efficiency have fewer staff options available.

For example, a job with minimum required efficiency of 10 can only be handled by staff with efficiency 10 or higher, but a job with minimum required efficiency of 5 can be handled by any staff with efficiency 5 or higher.

Greedy Strategy: 1. Process jobs in order of “decreasing minimum required efficiency” 2. For each job, assign the staff with the lowest efficiency among those who meet the condition

The reason for “choosing the staff with lowest efficiency” is that higher-efficiency staff might be usable for later jobs with stricter requirements, so we want to save them.

Concrete Example

• Staff efficiencies: [3, 5, 8]
• Job minimum required efficiencies: [6, 4, 2]

Processing in order of decreasing minimum required efficiency: 1. Job with minimum required efficiency 6 → Assign staff with efficiency 8 (minimum that satisfies condition) 2. Job with minimum required efficiency 4 → Assign staff with efficiency 5 3. Job with minimum required efficiency 2 → Assign staff with efficiency 3

Result: All 3 jobs can be completed

Algorithm

1. Calculate the minimum required efficiency \(\lceil D_j / T_j \rceil\) for each job \(j\)
2. Sort jobs in decreasing order of minimum required efficiency
3. Manage staff efficiencies using a SortedList (balanced binary search tree)
4. Process each job in order:
   • Use binary search to find a staff member with efficiency at or above the minimum required efficiency
   • If found, assign the staff with minimum efficiency among those found (remove from list) and increment the count
5. Output the final count

Complexity

• Time Complexity: \(O((N + M) \log N)\)
  • Sorting staff: \(O(N \log N)\)
  • Sorting jobs: \(O(M \log M)\)
  • Processing each job: \(O(M \log N)\) (binary search and deletion are each \(O(\log N)\))
• Space Complexity: \(O(N + M)\)
  • Arrays to store staff and job information

Implementation Notes

1. Ceiling Function Calculation: \(\lceil D_j / T_j \rceil\) can be computed using integer arithmetic as (D + T - 1) // T.

2. Using SortedList: Since Python’s standard library doesn’t have a balanced binary search tree, we use SortedList from the sortedcontainers library. This enables \(O(\log N)\) insertion, deletion, and binary search.

3. Using bisect_left: available.bisect_left(min_v) returns the index of the smallest element that is at least min_v. If the index is less than the array length, a staff member satisfying the condition exists.

Source Code

import sys
from sortedcontainers import SortedList

def solve():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    V = []
    for i in range(N):
        V.append(int(input_data[idx])); idx += 1
    
    jobs = []
    for j in range(M):
        D = int(input_data[idx]); idx += 1
        T = int(input_data[idx]); idx += 1
        jobs.append((D, T))
    
    # Condition for staff to handle job j: D_j <= V_i * T_j
    # That is, V_i >= D_j / T_j (integer at least ceil(D_j / T_j))
    # Minimum required efficiency = ceil(D_j / T_j) = (D_j + T_j - 1) // T_j
    
    # Greedy approach: Process jobs in order of decreasing minimum required efficiency,
    # and assign the staff with lowest efficiency among those who meet the condition
    
    # Calculate minimum required efficiency for each job
    job_requirements = []
    for j, (D, T) in enumerate(jobs):
        min_v = (D + T - 1) // T  # ceil(D/T)
        job_requirements.append((min_v, j))
    
    # Sort in decreasing order of minimum required efficiency
    job_requirements.sort(reverse=True)
    
    # Manage staff efficiencies using SortedList
    available = SortedList(V)
    
    count = 0
    for min_v, j in job_requirements:
        # Find the minimum efficiency staff among those with efficiency >= min_v
        idx_staff = available.bisect_left(min_v)
        if idx_staff < len(available):
            # A staff member satisfying the condition exists
            available.pop(idx_staff)
            count += 1
    
    print(count)

if __name__ == "__main__":
    solve()

---

This editorial was generated by claude4.5opus.