K-е наибольшее четное число в интервалах N

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

Примеры :

Input: arr = {{12, 15}, {3, 9}, {2, 5}, {20, 25}, {16, 20}}, K = 9
Output: 6
Explanation: After merging, the ranges become {{2, 9}, {12, 25}} the, even numbers present in the ranges are {2, 4, 6, 8, 12, 14, 16, 18, 20, 22, 24} and the 9th largest even number is 6

Input: arr = {{2, 4}, {8, 12}}, K = 4
Output: 4

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

• Если K<=0 или N=0, то вернуть -1
• Инициализировать, L = arr[i].first и R = arr[i].second
• Инициализировать диапазон переменных, чтобы хранить четные числа в диапазоне
• Итерация в цикле от idx до 0
  • Если R нечетное
    • диапазон = пол ((R – L + 1) / 2)
    • Если, K > диапазон K = K – диапазон
    • В противном случае верните R – 2 * K + 1
  • Если R даже
    • диапазон = ceil((с плавающей запятой)(R – L + 1)/2)
    • Если, K > диапазон K = K – диапазон
    • Иначе R – 2 * K + 2
• Возврат -1

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

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