Сперва для каждого ресторана нужно выписать тройку чисел – какое место этот ресторан занимает в списке каждого из мстителей. После этого сравнивать пару ресторанов становится очень легко – тот у которого хотя бы два числа из тройки меньше, тот и лучше. А значит можно поступить так: сперва одним проходом найти потенциально-лучший ресторан (каждый раз сравнивать текущий лучший с новым и обновлять, если потребуется), а затем еще одним проходом проверить является ли этот ресторан действительно лучшим. Сложность этого решения всего O(N).