Минимизируйте операции, чтобы сделать минимальное значение одного массива больше, чем максимальное значение другого

Даны два массива A[] и B[] , состоящие из N и M целых чисел, задача состоит в том, чтобы найти минимальное количество операций, необходимых для того, чтобы минимальный элемент массива A[] был как минимум максимальным элементом массива B[] так что в каждой операции любой элемент массива A[] может быть увеличен на 1 или любой элемент массива B[] может быть уменьшен на 1 .

Примеры:

Input: A[] = {2, 3}, B[] = {3, 5}
Output: 3
Explanation:
Following are the operations performed:

1. Increase the value of A[1] by 1 modifies the array A[] = {3, 3}.
2. Decrease the value of B[2] by 1 modifies the array B[] = {3, 4}.
3. Decrease the value of B[2] by 1 modifies the array B[] = {3, 3}.

After the above operations, the minimum elements of the array A[] is 3 which is greater than or equal to the maximum element of the array B[] is 3. Therefore, the total number of operations is 3.

Input: A[] = {1, 2, 3}, B[] = {4}
Output: 3

Подход: проблема может быть решена с помощью жадного подхода. Выполните следующие шаги, чтобы решить данную проблему:

• Отсортируйте массив A[] в порядке возрастания.
• Отсортируйте массив B[] в порядке убывания.
• Пройдите оба массива , пока A[i] < B[i] , чтобы сделать все элементы массивов A[] и B[] , до индекса i , равным, скажем, x , тогда общее количество операций дано по:

=> (B[0] + B[1] + … + B[i]) – i*x + (A[0] + A[1] + … + A[i]) + i*x
=> (B[0] – A[0]) + (B[1] – A[1]) + … + (B[i] – A[i]).

• Перемещайтесь по обоим массивам до тех пор, пока значение A[i] не станет меньше, чем B[i] , а значение (B[i] – A[i]) не станет равным переменной, скажем, ans .
• После выполнения вышеуказанных шагов выведите значение ans как минимальное количество требуемых операций.

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

Временная сложность: O(K*log K), где значение K равно max(N, M).
Вспомогательное пространство: O(1)