Daily bit(e) of C++ | Maximum number of invitations
Daily bit(e) of C++ #84, Common C++ interview problem: Maximum number of invitations
Today we will look at a common interview problem: Maximum number of invitations.
Given an array of integers, where each integer represents the seating preference (i.e. “pref[i] == j” means that person “i” wants to sit next to person “j”), determine the maximum number of people you can invite to sit a circular table while satisfying seating preferences of all invitees.
For example, for the input {1,2,0,4,3,3,4}, the best we can do is four people, specifically 3,4,5 and 6, because 3 and 4 want to sit next to each other, allowing 5 and 6 to sit next to 3 and 4, respectively.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/qjj69c1MM.
Solution
This type of problem requires some initial analysis. When can we sit people around a table without conflict?
The most obvious situation is a cycle: A→B→C→…→X→A
Since we can only seat one cycle at the table, the number of people is simply the length of the cycle.
However, there is a second option. Consider a pair of people that want to sit next to each other. They form a cycle of size two but also enable other people to sit next to them: A→B→X←→Y←C←D
Each group is standalone, allowing us to seat as many as we want around the table.
To determine the maximum number of people we can invite, we need two things. We must detect cycles and calculate the longest paths that terminate in cycles.
Fortunately, topological sort is a linear runtime algorithm that can provide this information.
