Минимизируйте значение уравнения (yi + yj + |xi – xj|), используя заданные точки

Дан массив arr[] размера N , где arr[i] имеет форму _{[xi ,} yi], обозначающую точку _{(xi ,} yi) на двумерной плоскости. Массив отсортирован по x-координатам. Кроме того, дано целое число K. Задача состоит в том, чтобы минимизировать значение уравнения y _i + y _j + |x _i – x _j | где |x _i – x _j | ≤ K и 1 ≤ я < j ≤ N . Гарантируется, что существует хотя бы одна пара точек, удовлетворяющих ограничению |x _i – x _j | ≤ К.

Примеры:

Input: arr[4] = {{1, 3}, {2, 0}, {5, 10}, {6, -10}}, K = 1
Output: 1
Explanation: The first two points satisfies the given condition |x_i – x_j| ≤ 1. 
Now, the equation  =  3 + 0 + |1 – 2| = 4. 
Similarly, Third and fourth points also satisfy the condition and 
give a value of 10 + -10 + |5 – 6| = 1. 
Except these 2 pairs no other points satisfy the given condition. 
Minimum of 4 and 1 is 1. So output is 1.

Input: arr[4] = {{0, 0}, {3, 0}, {9, 2}}, K = 3
Output: 3
Explanation: Only the first two points have an absolute difference of 3. 
It gives the value of 0 + 0 + |0 – 3| = 3.

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

• Инициализировать очередь с минимальным приоритетом minh[].
• Инициализируйте переменную min_val как INT_MAX .
• Перебрать диапазон [0, n), используя индекс переменной, и выполнить следующие задачи:
  • Выталкивайте элементы из min-кучи minh[] до тех пор, пока разница в координатах x не превысит K .
  • Если куча не пуста, обновите значение min_val.
  • Нажмите значение {arr[index][1] – arr[index][0], arr[index][0]}.
• После выполнения вышеуказанных шагов выведите значение min_val в качестве ответа.

Ниже приведена реализация описанного выше подхода.

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