Fill the boxes

3.4

9 votes
Basic Programming, Basics of Implementation, Implementation, Medium, Sorting, Two pointer
Problem

You are given an array of size N, denoting capacity of N boxes, and an integer K, denoting extended capacity factor. You are also given the weights of M balls. Each ith box can accommodate exactly one ball having weight in range [capacityi,capacityi+K] (both inclusive). Find the maximum number of boxes that can be filled.

Constraints:

  • 1T50
  • 1N,M10000
  • 1K1000
  • 1Capacityi1000
  • 1Weighti2000

Input format:
First line: T i.e. Number of test cases.
For each test case:
First line: Three space-separated integers N, M and K.
Second line: N space-separated integers denoting the capacity of boxes.
Third line: M space-separated integers denoting the weight of balls.

Output format:
For each test case, print the answer in a separate line.

Sample Input
1
3 2 1
1 4 3
6 2
Sample Output
1
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

In best scenario we can put ball 2 in box 1 hence answer is 1.

Editor Image

?