All problems

Skate Fitting Desk

Medium · two pointers

An ice rink rents out skates. The list skates holds the size of every pair of rental skates, and the list feet holds the foot size of every customer waiting at the desk. Both lists are sorted from smallest to largest, and equal values may repeat.

A pair of skates fits a customer when their sizes differ by at most tol, in either direction. Each pair of skates can be rented to only one customer, and each customer takes at most one pair.

Return the largest number of customers who can be given a pair of skates that fits them. If nobody can, return 0.

Examples

Example 1

Input: skates = [6, 8, 10, 13], feet = [5, 9, 9, 14], tol = 1

Output: 4

Give 6 to foot 5, 8 to the first 9, 10 to the second 9 and 13 to foot 14. Every customer is fitted.

Example 2

Input: skates = [2, 4, 6], feet = [3, 5], tol = 0

Output: 0

With a tolerance of 0 the sizes must match exactly, and no skate size equals a foot size.

Example 3

Input: skates = [7, 7, 9], feet = [7, 7, 7, 8], tol = 1

Output: 3

There are only three pairs of skates, and all three can be given to a customer they fit.

Constraints