Jars and lids
A canning kitchen has N jars and M lids, each with a diameter in millimetres. A lid seals a jar if the lid is at least as wide as the jar and at most T millimetres wider. Every lid can be used on one jar at most and every jar takes one lid at most. Read N, M and T, then the jar diameters and the lid diameters, and print the greatest number of jars that can be sealed.
Input
The first line has N, M and T separated by spaces. The second line has N jar diameters; the third line has M lid diameters.
Output
One line: the maximum number of sealed jars.
Example 1
Input
4 4 2 50 60 70 80 52 61 79 90
Output
2
Sorted, the jars are 50 60 70 80 and the lids 52 61 79 90. Lid 52 seals jar 50 and lid 61 seals jar 60. Jar 70 cannot use 79 (9 mm too wide) and jar 80 cannot use 90, so the answer is 2.
Example 2
Input
1 1 0 10 9
Output
0
A lid narrower than the jar never fits, whatever the tolerance.
Constraints
- 1 <= N, M <= 100000
- 1 <= each diameter <= 1000000000
- 0 <= T <= 1000000000
Hints
Hint 1 of 3
Sort both lists. Then the smallest jar should get the smallest lid that fits it: any larger lid that fits this jar would fit at least as many later jars, so giving away the smallest loses nothing.
Hint 2 of 3
Walk the jars in ascending order with an index into the sorted lids: skip lids narrower than the current jar; if the next lid is within tolerance use it and advance both, otherwise this jar can never be sealed, so move to the next jar without consuming a lid.
Hint 3 of 3
Diameters up to 10^9 fit in u64; sort_unstable is fine because equal values are interchangeable.
Solution
Show a reference solution and explanation
use std::io::{self, BufRead};
fn read_numbers(line: &str) -> Vec<u64> {
line.split_whitespace().map(|x| x.parse().unwrap()).collect()
}
fn main() {
let stdin = io::stdin();
let mut lines = stdin.lock().lines();
let header = read_numbers(&lines.next().unwrap().unwrap());
let tolerance = header[2];
let mut jars = read_numbers(&lines.next().unwrap().unwrap());
let mut lids = read_numbers(&lines.next().unwrap().unwrap());
jars.sort_unstable();
lids.sort_unstable();
let mut sealed = 0;
let mut li = 0;
for &jar in &jars {
while li < lids.len() && lids[li] < jar {
li += 1;
}
if li == lids.len() {
break;
}
if lids[li] - jar <= tolerance {
sealed += 1;
li += 1;
}
}
println!("{}", sealed);
}
Why it works
After sorting, a single left-to-right pass with two indices finds the optimum. The greedy rule is: the smallest unsealed jar takes the smallest lid that is wide enough, and if that lid is too wide the jar is abandoned. Abandoning is safe because every remaining lid is at least as wide as the one that was too wide, so none of them fits this jar either. Taking the smallest fitting lid is safe because if some optimal matching gave this jar a wider lid, swapping to the smaller one keeps this jar sealed and can only make the wider lid available to a later, larger jar. Sorting costs O((N + M) log(N + M)) and the pass is linear. The subtle case is lids narrower than the current jar: they must be skipped, not treated as a failure for that jar.