Найдите индексы K самых больших пар в порядке убывания произведения из заданного массива пар

Дан массив arr[] из N целочисленных пар и целое число K , задача состоит в том, чтобы найти индексы K самых больших пар в порядке убывания произведения.

Пример:

Input: arr[] = {{9, 1}, {6, 3}, {6, 8}, {4, 5}, {1, 8}}, K = 1
Output: 2
Explanation: The pair with the largest product is at index 2 i.e, {6, 8}.

Input: arr[] = {{1, 2}, {1, 4}, {1, 3}, {1, 5}}, K = 4
Output: 3 1 2 0

Подход: Данную задачу можно решить с помощью жадного подхода. Идея состоит в том, чтобы сохранить пару (продукт, индекс) для каждой из заданных пар данного массива в векторе пар и отсортировать вектор пар в порядке убывания их значения продукта. Значение индекса первых K пар является требуемым ответом.

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

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