Максимизируйте количество возрастающих троек из любой перестановки заданных 3 массивов

Даны три массива X[] , Y[] и Z[] , каждый из которых состоит из N целых чисел, задача состоит в том, чтобы найти максимальное количество троек (X[i], Y[i], Z[i]) , таких что ( X[i] < Y[i] < Z[i]) для любой перестановки трех массивов.

Примеры:

Input: X = {9, 6, 14, 1,  8}, Y = {2, 10, 3, 12, 11}, Z = {15, 13, 5, 7, 4}
Output: 3
Explanation:  
After rearranging the arrays X[], Y[] and Z[] as {1, 6, 8, 9, 14}, {3, 2, 10, 12, 11}, and {4, 7, 15, 13, 5} respectively. The increasing triplets are {1, 3, 4}, {8, 10, 15} and {9, 12, 13}.
Therefore, the total count of such triplets is 3.

Input: X = {1, 2, 3, 4}, Y = {5, 6, 7, 8}, Z = {9, 10, 11, 12}
Output: 4

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

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

Эффективный подход: данная проблема может быть решена с использованием жадного подхода, идея состоит в том, чтобы отсортировать заданный массив X [], а затем для поиска троек выбрать те элементы в массиве Y [] и Z [] , которые образуют возрастающие тройки для каждый элемент массива, и эту идею можно реализовать с помощью приоритетной очереди. Выполните следующие шаги, чтобы решить проблему:

• Отсортируйте массив X[] в порядке возрастания.
• Инициализируйте две приоритетные очереди, скажем, PQY и PQZ, реализующие MinHeap для массива Y[] и Z[] соответственно.
• Сохраните все элементы массива Y[] в PQY .
• Сохраните все элементы массива Z[] в PQZ .
• Перейдите массив X[] и выполните следующие шаги:
  • Для каждого элемента X[i] извлекайте элемент из приоритетной очереди PQY до тех пор, пока его верхний элемент не станет меньше X[i] и PQY не станет пустым.
  • Для каждого элемента верхнего элемента PQY , скажем, temp, извлекайте элемент из приоритетной очереди PQZ до тех пор, пока его верхний элемент не станет меньше, чем temp , а PQY не будет пустым.
  • Увеличьте значение count на 1 .
• После выполнения вышеуказанных шагов выведите значение count как результирующее максимальное количество триплетов.

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

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