CODEWITHSUNDEEP
algorithmdata-structures
user2912611
user2912611

Reputation: 544

Arrange players in football team according to their heights

I've been recently asked this question in an interview. Question is as follows:

Given heights of player of two football teams in array A and array B respectively. Now, you have to tell if you can arrange the team for photograph with following constraint.

  1. One Team will be standing in one row (All players of one team must be together).
  2. Height of player of one team standing in front should be lesser than the height of player of other team standing behind him.

Follow up question to this was, what if there are N teams what would be the maximum number of team K you can select for photograph such that they would follow the above constraints.

I came up with the solution for 2 team but couldn't think of solution for the follow up question.

Upvotes: 3

Views: 603

Answers (2)

btilly
btilly

Reputation: 46408

Given two teams we can tell whether both can be in the picture together, and if so then which is in front. As @typewriter says, this results in a partial order. This partial order can be represented as an acyclic directed graph.

At this point we can apply any well-known Topological Sort algorithm to come up with a linear order.

And now we process the teams in that order, and store the following two pieces of information for each team:

  1. How many teams can be in front of this in the picture?

  2. What is the next team in front of them in that maximal picture?

(We determine this by picking the previous team that can be in the same picture with the largest possible picture. We mark that as the next team, and this team can have one more team in the picture. This is an example of a dynamic programming algorithm.)

When we are done processing the entire list, look for the team which can have the most teams in front of them. And then walk the data structure in order to figure out which teams should be in the picture.

If there are N teams of M players, this algorithm should run in O((N + log(M)) * N * M). The O(log(M) * N * M) bit is from N sorts of the individual teams. The O(N^2 * M) bit is from finding all of the team pairwise comparisons. The topological sort and dynamic programming bit are fast relative to the second step.

Upvotes: 3

typewriter
typewriter

Reputation: 368

It is an interesting question. For two teams you can sort both teams by length. If the $n$-th member in team A is longer than the $n$-th member in team B, then the teams are comparable in a POSET sense. I.e. you can say that team A is longer than team B.

Not every team is comparable in this way. The sorted teams increase in height, but increasing functions may still intersect. Since not every pair of teams is comparable, the collection of all teams is called a partially ordered set or POSET. You may want to take a look at this: https://people.math.gatech.edu/~trotter/math-3012/3012-Lecture-14.pdf.

The follow up part of the question could be interpreted as finding the height of this POSET. i.e. what is the largest number of teams that could fit in one photo.

I could find no explicit algorithm in googling, but am sure it exists.

Upvotes: 1

Related Questions