We are going to hold a meeting where everybody will speak in clockwise direction around a table. There are n people with n spots. Each person has a position preference (e.g. some want to go first, some last, etc). Everyone is seated randomly and cannot move from their position. How shall we compute the best starting position on the table to satisfy the most people?
I have an O(n^2) solution:
See how many people would be satisfied having assumed each of the positions 1..n as start positions; then return the position that gave the maximum value.
5
A fairly simple O(n) algorithm exists:
Let pos be an array so that if the person at seat i wants to speak as n-th, we have an entry pos[i] = n. Where the numbering of the seats starts is irrelevant. Both i and n start counting with zero.
The difference i - pos[i] is the seat where the round would have to start for the person at seat i to be satisfied. We count the satisfied persons per start position in a satisfied array. We can then find the maximum of that array, the index of the maximum is the seat where the round should start for maximum satisfaction.
Java example:
int findBestStart(int[] pos) {
// ask each seat where they'd like to start
int[] satisfied = new int[pos.length];
for (int i = 0; i < pos.length; i++) {
int start = i - pos[i]
if (start < 0) start += pos.length;
satisfied[start]++;
}
// find where most would like to start
int bestSeat = -1;
int bestSatisfied = -1;
for (int i = 0; i < satisfied.length; i++) {
if (satisfied[i] > bestSatisfied) {
bestSeat = i;
bestSatisfied = satisfied[i];
}
}
return bestSeat;
}
4
If each person knows exactly what order he wants to go in and the seating order is constant, then each person knows what starting position he wants the speaking to start at. This way, you can calculate how many people want speaking start at specific points, which is O(n) in complexity if you the preferred position as index into array.
2