Overview

There are \(N\) staff members and \(M\) jobs. Each staff member can be assigned to at most one job that meets certain conditions, and the goal is to find the maximum number of jobs that can be completed. This is a “maximum matching” problem where we compare each staff member’s ability with each job’s requirement, but it can be solved efficiently using sorting and a greedy approach.

Analysis

1. Organizing the Conditions

The condition for staff member \(i\) to be able to handle job \(j\) is \(D_j \leq V_i \times T_j\). Rearranging this with respect to the staff member’s work efficiency \(V_i\), we get: $\(V_i \geq \frac{D_j}{T_j}\)\( Since \)V_i\( is an integer, if we let \)R_j\( be the minimum work efficiency required to complete job \)j\(, then: \)\(R_j = \lceil \frac{D_j}{T_j} \rceil \quad (\text{ceiling of \)D_j / T_j\(})\)$ In code, ceiling division for integers is commonly written as (D + T - 1) // T.

2. Applying the Greedy Approach

This problem can be rephrased as: “What is the maximum number of pairs we can form where ability \(V_i\) is at least as large as requirement \(R_j\)?” In such cases, the optimal greedy strategy is: “For jobs with smaller requirements, assign the staff member with the lowest ability who can still handle the job.” This is because if we assign a highly capable staff member to an easy job, there may be no staff left who can handle the harder (higher requirement) jobs that come later.

Algorithm

1. Calculate required efficiencies: For each job \(j\), compute the minimum required efficiency \(R_j = \lceil D_j / T_j \rceil\) and store it in a list.
2. Sort: Sort both the staff ability list \(V\) and the job requirement list \(R\) in ascending order (from smallest to largest).
3. Two-pointer traversal:
   • Prepare a pointer v_ptr for staff and a pointer r_ptr for jobs.
   • If V[v_ptr] >= R[r_ptr], then that staff member can handle that job.
     • Count the job as completed and advance both pointers.
   • If V[v_ptr] < R[r_ptr], then that staff member cannot handle the current job (or any harder jobs).
     • Advance only the staff pointer v_ptr to look for a more capable staff member.
4. Repeat until either pointer reaches the end, then output the number of completed jobs.

Complexity

• Time complexity: \(O(N \log N + M \log M)\)
  • Computing required efficiencies takes \(O(M)\), sorting takes \(O(N \log N + M \log M)\), and the two-pointer traversal takes \(O(N + M)\). The sorting step is dominant.
• Space complexity: \(O(N + M)\)
  • Memory is needed to store the staff abilities and job requirements.

Implementation Notes

• Fast I/O: Since \(N, M\) can be as large as \(2 \times 10^5\), in Python it is faster to read all input at once using sys.stdin.read().split() rather than calling input() repeatedly.

• Ceiling division: Using floating-point numbers (D / T) may cause precision errors with very large values, so it is safer to use integer arithmetic (D + T - 1) // T.

  Source Code

import sys

def solve():
    # Read all input at once and split by whitespace for efficiency
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    it = iter(input_data)
    
    # Read N (number of staff) and M (number of jobs)
    try:
        N = int(next(it))
        M = int(next(it))
    except StopIteration:
        return
    
    # Read staff work rates V
    V = [0] * N
    for i in range(N):
        V[i] = int(next(it))
        
    # Read job requirements D (workload) and T (time limit)
    # Calculate the minimum required work rate V_i for each job
    # The condition D_j <= V_i * T_j is equivalent to V_i >= D_j / T_j
    # Since V_i must be an integer, V_i >= ceil(D_j / T_j)
    R = [0] * M
    for i in range(M):
        D = int(next(it))
        T = int(next(it))
        # Integer calculation for ceil(D / T)
        R[i] = (D + T - 1) // T
        
    # Sort both staff work rates and job requirements in non-decreasing order
    V.sort()
    R.sort()
    
    # Use a greedy strategy with two pointers to find the maximum matching
    # We try to satisfy the smallest job requirement with the smallest possible staff work rate
    v_ptr = 0
    r_ptr = 0
    ans = 0
    
    while v_ptr < N and r_ptr < M:
        if V[v_ptr] >= R[r_ptr]:
            # This staff member is efficient enough to handle the current smallest job requirement
            ans += 1
            v_ptr += 1
            r_ptr += 1
        else:
            # This staff member is not efficient enough for the current job requirement.
            # Since requirements are sorted, this staff won't be able to handle any subsequent jobs.
            # Move to the next, more efficient staff member.
            v_ptr += 1
            
    # Output the maximum number of jobs that can be completed
    print(ans)

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-preview.