Intern Allocation To Manager Based On The Best Preference Match

Design a intern allocation system based on the preference of interns and managers.
For e.g. 5 intern gives their preferences for 5 manager and vice versa.
The match should be done based on the best possible match.

Intern 1 Chooses
        Manager 1, Manager 3, Manager 4, Manager 2 and Manager 5 as the preference.
Manager 1 Chooses 
        Intern 2, Intern 3, Intern 4, Intern 5 and Intern 1 as the preference.

Similarly for all other 4 interns and 4 manager.

Expected Output:
Intern 1 works with Manager 3

Intern 2 works with Manager 2

Intern 3 works with Manager 1

Intern 4 works with Manager 4

Intern 5 works with Manager 5

1) Based on the problem description we can have matrix for interns and managers with the weights as preferences.
2) Do a customized matrix multiplication of both the matrix
3) Sort them using Tree Set to get the sorted records and find the first five or find a unique allocation with intermediate matrix.

Input:
Interns Weighted Preference

5  2  4  3  1
2  5  4  3  1
5  4  3  2  1
2  5  4  3  1
2  1  5  4  3

Managers Weighted Preference

2  1  5  4  3
2  5  4  3  1
2  1  5  4  3
5  4  3  2  1
2  5  4  3  1

Intermediate Output:

Multiplied Matrix
---------------------
10  2     20  12  3
4    25  16    9  1
10  4    15    8  3
10  20  12    6  1
4    5    20  12  3

Intern Allocation
---------------------
0   0   20  0  0
0   25  0   0  0
10  0   0   0  0
0    0   0   6  0
0    0   0   0  3

Ouput:

Intern 1 works with Manager 3

Intern 2 works with Manager 2

Intern 3 works with Manager 1

Intern 4 works with Manager 4

Intern 5 works with Manager 5
-------------------------------------------------------------------

InternAllocation.java

InternAllocationDemo.java