For the following problem, decide if the provided answer correctly solves the problem. If it does then analyze the running time of the algorithm. If it does not, give an example demonstrating why not.

Problem: Given n people, n jobs, and a table of distinct rewards for assigning people to jobs - i.e. is the reward for assigning a person to a job; find the maximum total reward that can be achieved by a matching of people to jobs (i.e. exactly one person per job).

Solution: Use the table of rewards to set up a preference relation - e.g. Person i prefers job j₁to j₂ if R(i,j₁) > R(i,j₂); and job j prefers to be assigned to person i₁ over i₂ if R(i₁,j)> R(i₂,j) . Run the Gale-Shapley algorithm to find a matching. Compute the reward for this matching. This will be the maximum reward.