Сумма всех целых чисел в заданных N диапазонах

Учитывая N диапазонов формы [L, R] , задача состоит в том, чтобы найти сумму всех целых чисел, которые лежат в любом из заданных диапазонов.

Примеры :

Input: arr[] = {{1, 5}, {3, 7}}, N = 2
Output: 28
Explanation: The set of integers that exist in one or more ranges is {1, 2, 3, 4, 5 , 6, 7}. Hence there sum is 28.

Input: ranges[] = {{-12, 15}, {3, 9}, {-5, -2}, {20, 25}, {16, 20}}
Output: 247

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

• Отсортируйте интервалы на основе возрастающего порядка L .
• Поместите первый интервал в стек и для каждого интервала выполните следующие действия:
  • Если текущий интервал не перекрывается с вершиной стека, нажмите его.
  • Если текущий интервал перекрывается с вершиной стека, а правый конец текущего интервала больше, чем у вершины стека, обновите вершину стека со значением правого конца текущего интервала.
• После обхода всех интервалов оставшийся стек содержит объединенные интервалы. Сумма объединенных интервалов может быть рассчитана по формуле суммы арифметической прогрессии, поскольку диапазон [L, R] образует ПД с общей разностью, равной 1 , и количеством элементов, равным R – L + 1 . Сумма равна ((L + R)*(R-L+1))/2.

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

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