Добавьте интервал минимального размера, чтобы все интервалы сливались в один

Учитывая двумерный массив arr размера N , который представляет интервал [начало, конец] включительно, где (начало < конец) , задача состоит в том, чтобы добавить только один интервал минимального размера (размер = конец - начало) в данный arr , так что объединение всех интервалов дает только один интервал.

Примеры:

Input: arr= {{12, 20}, {24, 100}}
Output: 4
Explanation: We can add the interval [20, 24] which is the smallest possible interval.

Input: arr= {{21, 43}, {26, 29}, {46, 70}}
Output: 3

Подход: Жадный алгоритм:

The idea to solve this problem is that we’ll try to add intervals greedily. Since we know there is a single interval missing, we want to track the gap when adding the intervals in a sorted manner from start to end. 

We can do this by keeping the track of the last interval’s end and new interval’s begin when the previous and the current intervals are non overlapping.

Выполните следующие шаги, чтобы реализовать вышеуказанную идею:

• Сначала отсортируйте интервалы по начальной позиции.
• Сохраните переменные « start» и « end» , в которых хранится начальная и конечная точка нашего требуемого интервала ответов. и дополнительная переменная « prev» для хранения последнего произошедшего интервала в итерации, необходимой для слияния для следующих предстоящих интервалов.
• Проверьте, перекрываются ли интервалы или нет.
  • Если интервалы не перекрываются
    • Следите за «началом» и « концом»
    • Обновите « prev » с текущим интервалом arr[i].
  • Обновите « prev» после объединения перекрывающихся интервалов
• Верните размер интервала, используя конец-начало .

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

Временная сложность: O(N * logN), это связано с сортировкой.
Вспомогательное пространство: O(1)