Stone and Box

0

0 votes
Merge Sort, Sorting, Algorithms, Greedy Algorithms
Problem

You are given the following:

  • A: An array consists of N integers denoting the size of stones
  • B: An array consists of M integers denoting the size of boxes

You can place a stone into a box only when the size of the box is at least double the size of the stone. A box can contain only 1 stone at a time.

Task

You have to determine the maximum number of stones that can be put in boxes.

Note: 0-based indexing is followed.

Example

Assumption

  • N = 3
  • M = 2
  • A = [1, 2, 3]
  • B = [4, 8]

Approach

  • Put stone A[0] into box B[0].
  • Put stone A[2] into box B[1].

Therefore the maximum number of stones that can be put into the boxes is 2.

Note: There are other ways possible but the maximum number of stones that can be stored in the boxes is 2.

Function description

Complete the solve function provided in the editor. This function takes the following 4 parameters and returns the answer.

  • N: Represents an integer denoting the size of array A
  • M: Represents an integer denoting the size of array B
  • A: Represents an integer array
  • B: Represents the integer array

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

  • The first line contains two space-separated integers N anddenoting the size of arrays A and B.
  • The second line contains N space-separated integers denoting array A.
  • The third line contains M space-separated integers denoting array B.

Output format

Print a single integer denoting the maximum number of stones that can be stored into the boxes.

Constraints

1N1051M1051Ai1091Bi109

Code snippets (also called starter code/boilerplate code)

This question has code snippets for C, CPP, Java, and Python.

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Given

  • N = 3
  • M = 4
  • A = [3, 1, 2]
  • B = [2, 4, 3, 1]

Approach

  • Put stone A[1] into box B[0].
  • Put stone A[2] into box B[1].

Therefore the maximum number of stones that can be put into the boxes is 2.

Note: There are other ways possible but the maximum number of stones that can be stored in the boxes is 2.

Editor Image

?