Overview

A problem where we assign as many packages as possible out of \(M\) packages to \(N\) trucks (each truck has a weight limit and a quantity limit). We sort the trucks and packages, then use a greedy approach to find the maximum number of packages.

Analysis

Key Insight

First, brute force trying all assignment patterns would be on the order of \(O(N^M)\), which is far too slow given the constraints (\(N, M \leq 2 \times 10^5\)).

Here we consider a greedy approach. The key observations are:

• Lighter packages are more flexible: Packages with smaller weight can be loaded onto trucks with both small and large weight limits \(E_i\).
• Heavier packages are more restricted: Packages with larger weight can only be loaded onto trucks with sufficiently large \(E_i\).

Greedy Strategy

Process trucks in ascending order of weight limit \(E_i\). At the time each truck is processed, add the “candidate packages that can be loaded” to a pool.

Which packages should we choose from the pool? The answer is “prioritize using the lightest packages.”

Reason: Packages that can be loaded onto the current truck (with small \(E_i\)) can definitely also be loaded onto trucks processed later (with larger \(E_i\)). On the other hand, heavier packages not yet in the pool can only be loaded onto future trucks with large \(E_i\). Therefore, to reserve capacity on future trucks for heavy packages, it is optimal to assign light packages to the current truck.

Concrete Example

Truck A (\(E=5, C=2\)), Truck B (\(E=10, C=1\)), package weights \([3, 4, 8]\):

• When processing Truck A: \(\{3, 4\}\) enter the pool → assign 2 packages in order of lightest (\(3, 4\))
• When processing Truck B: \(\{8\}\) is added to the pool → assign 1 package (\(8\))
• Total of 3 packages can be delivered

If we took the heavier ones for Truck A, package 8 would compete for Truck B’s slot, potentially reducing the total.

Algorithm

1. Sort trucks in ascending order of \(E_i\)
2. Sort packages in ascending order of weight \(D_j\)
3. Prepare a pointer pkg_idx to manage sorted packages
4. Process trucks in order:
   • Add all packages satisfying \(D_{pkg\_idx} \leq E_i\) to the “available pool”
   • Take out \(\min(C_i, |\text{pool}|)\) lightest items from the pool and add to the delivery count
5. Output the final delivery count

Complexity

• Time complexity: \(O((N + M) \log M)\)
  • Sorting: \(O(N \log N + M \log M)\)
  • Adding to pool during each truck’s processing: \(O(M \log M)\) in total (each insertion into SortedList is \(O(\log M)\))
  • Deletion from pool: \(O(M)\) in total (slice deletion from SortedList is proportional to the number of elements deleted, at most \(M\) deletions total)
• Space complexity: \(O(N + M)\)

Implementation Notes

• Using SortedList: With Python’s sortedcontainers.SortedList, element insertion is \(O(\log M)\), and slice deletion from the front del available[:take] can be performed efficiently.

• Consistent sort order: By sorting both trucks and packages in ascending order, we can add “candidate packages that can be loaded” simply by advancing the pointer in one direction (a two-pointer technique idea).

• Focused on maximizing count: Since there is no constraint on the total weight of packages, we only need to determine whether each individual package can be loaded, avoiding the complexity of knapsack-like problems.

  Source Code

import sys
from sortedcontainers import SortedList

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    trucks = []
    for i in range(N):
        E = int(input_data[idx]); idx += 1
        C = int(input_data[idx]); idx += 1
        trucks.append((E, C))
    
    D = []
    for j in range(M):
        D.append(int(input_data[idx])); idx += 1
    
    # Greedy approach:
    # Sort trucks by E (weight limit) in ascending order.
    # Sort packages by weight in ascending order.
    # Process trucks in order of increasing E.
    # For each truck, all packages with D_j <= E_i become available.
    # Among available (unassigned) packages, we want to pick the C_i lightest ones
    # (greedy: use lightest packages for this truck, saving heavier ones for trucks with higher E).
    # Actually, we should pick the HEAVIEST available packages that fit, because
    # lighter packages are more flexible (can fit in more trucks).
    # Wait, let me reconsider...
    
    # Actually the optimal greedy: sort trucks by E ascending. For each truck,
    # among all available packages with D_j <= E_i, we should assign the HEAVIEST ones
    # to this truck. Because lighter packages can potentially fit in trucks with smaller E
    # that we haven't... wait, we process in ascending E order, so all future trucks have
    # E >= current E, meaning lighter packages will also fit in future trucks.
    # So we should assign the heaviest available packages (that fit) to the current truck,
    # keeping lighter ones for potentially being used by future trucks (which they'll fit in too).
    # But future trucks also accept heavier packages... 
    
    # Actually, the standard greedy for this type of problem:
    # Sort trucks by E ascending, sort packages by D ascending.
    # For each truck (ascending E), add all packages with D <= E to available pool.
    # Then greedily take the C_i smallest from the pool (to leave heavier for bigger trucks).
    # No wait... we want to maximize count, not minimize waste.
    
    # To maximize the number of packages delivered:
    # Sort trucks by E ascending. Sort packages by D ascending.
    # Maintain a pool of available packages. For each truck, add packages with D <= E.
    # From the pool, take up to C_i packages. Which ones? The lightest, because
    # heavier packages in the pool can only be used by trucks with E >= current E (future trucks),
    # so we should save them. Lighter packages can also be used by future trucks, but
    # by using them now we free up capacity for heavier packages later.
    # Actually since all packages in the pool fit in the current truck AND all future trucks,
    # it doesn't matter which we pick for count maximization... 
    # But packages added later (heavier) only fit in future trucks, not current.
    # So we should use the lightest ones now (they fit everywhere) to save capacity of 
    # future trucks for heavier packages that only fit there.
    # Yes: pick the lightest C_i from the pool.
    
    trucks.sort(key=lambda x: x[0])
    D.sort()
    
    # We need a data structure that supports:
    # - Adding elements
    # - Removing the smallest C_i elements efficiently
    # Use a SortedList and pop from the front
    
    available = SortedList()
    pkg_idx = 0
    total = 0
    
    for E, C in trucks:
        # Add all packages with D <= E
        while pkg_idx < M and D[pkg_idx] <= E:
            available.add(D[pkg_idx])
            pkg_idx += 1
        
        # Take up to C lightest packages
        take = min(C, len(available))
        if take > 0:
            total += take
            # Remove the smallest 'take' elements
            # SortedList supports slicing deletion
            del available[:take]
    
    print(total)

if __name__ == '__main__':
    main()

---

This editorial was generated by claude4.6opus-thinking.