Problem 349583 · easy · Phase 03 Linear Management & Searching

Parcels into Boxes

sorting · greedy · two pointers

You have parcels with sizes parcels[i] and boxes with capacities boxes[j]. A parcel fits into a box when capacity >= size. Every box holds at most one parcel and every parcel goes into at most one box.

Return the maximum number of parcels that can be shipped.

Examples

Input:  parcels = [1, 2, 3], boxes = [1, 1]
Output: 1
Explanation: Only the size-1 parcel fits into a capacity-1 box.
Input:  parcels = [1, 2], boxes = [1, 2, 3]
Output: 2

Constraints

  • 0 <= len(parcels), len(boxes) <= 10**5
  • 1 <= parcels[i], boxes[j] <= 10**9
  • Target complexity: O(n log n + m log m).

Goals

  • Sort both lists and match them with two pointers
  • Argue why the smallest box that fits should take the smallest parcel
  • Handle the case where one list runs out first
Starting Python…