Найдите, кто выиграл выборы на основе данной системы голосования

Дан массив пар arr[][] вида {X, Y} , где каждый arr[i] представляет время X , когда был проголосован кандидат с ID кандидата Y , и массив запросов query[] , состоящий из M положительные целые числа, задача для каждого запроса Q[i] состоит в том, чтобы найти ID кандидата-победителя на момент Q[i] голосования.

Примечание. В случае, если в данный момент времени есть 2 кандидата с одинаковым количеством голосов K , выведите кандидата, получившего эти голоса первым.

Примеры:

Input: arr[] = {{1, 2}, {2, 2}, {4, 1}, {5, 5}, {7, 1}, {11, 1}}, query[] = {2, 8, 12}
Output: 2 2 1
Explanation:
For query[0] = 2, at time 2, the candidate with candidateID = 2 has got the maximum votes.
For query[1] = 8, at time 8, the candidates with candidateID’s = 2 and 1 have got the maximum votes i.e, 2 but since candidate with ID 2 got those before so the answer is 2.
For query[2] = 12, at time 12, the candidate with candidateID = 1 has got the maximum votes i.e, 3.

Input: arr[] = {{1, 1}}, query[] = { 1 }
Output: 1

Подход: Данная проблема может быть решена путем предварительного вычисления победителя на каждом следующем временном интервале в массиве arr[] и сохранения его в другом массиве, скажем, Ans[] в виде {timeInterval,winkerCandidateID} и затем для каждого запроса query[ i] выполнить двоичный поиск в массиве Ans[] , чтобы получить победившего кандидата в момент времени query[i] . Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте вектор, скажем, Ans[] , который сохраняет победителя в каждом входящем временном интервале arr[i].first .
• Инициализируйте неупорядоченную карту, скажем, Map[] , которая хранит частоту идентификатора кандидата в каждый входящий временной интервал.
• Инициализируйте пару, скажем, previous[] , которая отслеживает кандидата-победителя.
• Вставьте первую пару в вектор Ans[] и отметьте ее как предыдущую.
• Переберите диапазон [1, N – 1], используя переменную i , и выполните следующие шаги:
  • Увеличьте частоту текущего кандидата arr[i].second на 1 в карте Map .
  • Если текущий кандидат до сих пор побеждает, то обновите пару предыдущих .
  • Вставьте предыдущий в вектор Ans[] .
• Переберите диапазон [0, M), используя переменную i , и выполните следующие шаги:
  • Для каждого запроса выполните бинарный поиск в векторе пар Ans[] , чтобы найти победившего кандидата.
  • Выполните бинарный поиск по времени, т. е. по первому значению вектора пар Ans[] и найдите наибольшее значение, которое меньше, чем равно query[ I ] , и выведите соответствующий идентификатор кандидата .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(max(N, M*log(N)))
Вспомогательное пространство: O(N)