TopCoder problem "BootsExchange" used in SRM 307 (Division II Level One)



Problem Statement

    

A boot shop has received a shipment from the factory consisting of N left boots and N right boots. Each boot has some integer size, and a left and right boot will form a proper pair if they have equal sizes. Each boot can only belong to a single pair. The employees of the boot store want to create N proper pairs of boots. Fortunately, the factory has offered to exchange any number of boots in the shipment with new boots of different sizes.

You are given a int[] left and a int[] right containing the sizes of the left boots and right boots, respectively. Return the least number of boots that must be exchanged.

 

Definition

    
Class:BootsExchange
Method:leastAmount
Parameters:int[], int[]
Returns:int
Method signature:int leastAmount(int[] left, int[] right)
(be sure your method is public)
    
 

Constraints

-Each element in left will be between 1 and 1000, inclusive.
-Each element in right will be between 1 and 1000, inclusive.
-left and right will have the same number of elements.
-left will contain between 1 and 50 elements, inclusive.
 

Examples

0)
    
{1, 3, 1}
{2, 1, 3}
Returns: 1
They can exchange a size 1 left shoe for a size 2 left shoe, or they can exchange the size 2 right shoe for a size 1 right shoe.
1)
    
{1, 3}
{2, 2}
Returns: 2
They can exchange both left shoes for size 2 left shoes, or they can exchange the right shoes for a size 1 right shoe and a size 3 right shoe, or they can mix these two possibilities.
2)
    
{1, 2, 3, 4, 5, 6, 7}
{2, 4, 6, 1, 3, 7, 5}
Returns: 0
Nothing to exchange.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6081

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9987&pm=6081

Writer:

Mike Mirzayanov

Testers:

PabloGilberto , brett1479 , Olexiy , marian

Problem categories:

Greedy