Dados N rangos de la forma [L, R] , la tarea es encontrar la suma de todos los números enteros que se encuentran en cualquiera de los rangos dados.
Ejemplos :
Entrada : arr[] = {{1, 5}, {3, 7}}, N = 2
Salida : 28
Explicación: El conjunto de enteros que existen en uno o más rangos es {1, 2, 3, 4, 5 , 6, 7}. Por lo tanto, la suma es 28.Entrada : rangos[] = {{-12, 15}, {3, 9}, {-5, -2}, {20, 25}, {16, 20}} Salida
: 247
Enfoque: el problema dado se puede resolver mediante un enfoque similar al problema de combinación de intervalos superpuestos . A continuación se detallan los pasos a seguir:
- Ordene los intervalos según el orden creciente de L .
- Empuje el primer intervalo en una pila y para cada intervalo haga lo siguiente:
- Si el intervalo actual no se superpone con la parte superior de la pila, empújelo.
- Si el intervalo actual se superpone con la parte superior de la pila y el extremo derecho del intervalo actual es mayor que la parte superior de la pila, actualice la parte superior de la pila con el valor del extremo derecho del intervalo actual.
- Después de recorrer todos los intervalos, la pila restante contiene los intervalos fusionados. La suma de los intervalos combinados se puede calcular utilizando la fórmula para la suma de una progresión aritmética cuando el rango [L, R] forma un AP con una diferencia común como 1 y el número de elementos como R – L + 1 . La suma es ((L + R)*(R-L+1))/2.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
#define ll long long
using namespace std;
// Function to find the sum of all
// integers numbers in range [L, R]
ll sumInRange(long L, long R)
{
ll Sum = ((R - L + 1) / 2)
* (2 * L + (R - L));
return Sum;
}
// Function to find sum of all integers
// that lie in any of the given ranges
ll calcSum(vector<pair<long, long> > data,
int n)
{
// Sort intervals in increasing order
// according to their first element
sort(data.begin(), data.end());
// Merging the overlapping intervals
int i, idx = 0;
// Loop to iterate through the array
for (i = 1; i < n; i++) {
// If current interval overlaps
// with the previous intervals
if ((data[idx].second >=
data[i].first)
|| (data[i].first ==
data[idx].second + 1)) {
// Merge the previous and the
// current interval
data[idx].second
= max(data[idx].second,
data[i].second);
}
else {
idx++;
data[idx].second = data[i].second;
data[idx].first = data[i].first;
}
}
// Stores the required sum
ll Sum = 0;
// Loop to calculate the sum of all
// the remaining merged intervals
for (i = 0; i <= idx; i++) {
// Add sum of integers
// in current range
Sum += sumInRange(data[i].first,
data[i].second);
}
// Return the total Sum
return Sum;
}
// Driver Code
int main()
{
vector<pair<long, long> > vec
= { { -12, 15 },
{ 3, 9 },
{ -5, -2 },
{ 20, 25 },
{ 16, 20 } };
cout << calcSum(vec, vec.size());
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to find the sum of all
// integers numbers in range [L, R]
static int sumInRange(int L, int R)
{
int Sum = ((R - L + 1) / 2)
* (2 * L + (R - L));
return Sum;
}
// Function to find sum of all integers
// that lie in any of the given ranges
static int calcSum(int [][]data,
int n)
{
// Sort intervals in increasing order
// according to their first element
Arrays.sort(data,(a,b)->{
return a[0]-b[0];
});
// Merging the overlapping intervals
int i, idx = 0;
// Loop to iterate through the array
for (i = 1; i < n; i++) {
// If current interval overlaps
// with the previous intervals
if ((data[idx][1] >=
data[i][0])
|| (data[i][0] ==
data[idx][1] + 1)) {
// Merge the previous and the
// current interval
data[idx][1]
= Math.max(data[idx][1],
data[i][1]);
}
else {
idx++;
data[idx][1] = data[i][1];
data[idx][0] = data[i][0];
}
}
// Stores the required sum
int Sum = 0;
// Loop to calculate the sum of all
// the remaining merged intervals
for (i = 0; i <= idx; i++) {
// Add sum of integers
// in current range
Sum += sumInRange(data[i][0],
data[i][1]);
}
// Return the total Sum
return Sum;
}
// Driver Code
public static void main(String[] args)
{
int [][]vec
= { { -12, 15 },
{ 3, 9 },
{ -5, -2 },
{ 20, 25 },
{ 16, 20 } };
System.out.print(calcSum(vec, vec.length));
}
}
// This code is contributed by shikhasingrajput
Python3
# Python 3 program for the above approach # Function to find the sum of all # integers numbers in range [L, R] def sumInRange(L, R): Sum = ((R - L + 1) // 2) * (2 * L + (R - L)) return Sum # Function to find sum of all integers # that lie in any of the given ranges def calcSum(data, n): # Sort intervals in increasing order # according to their first element data.sort() # Merging the overlapping intervals idx = 0 # Loop to iterate through the array for i in range(1, n): # If current interval overlaps # with the previous intervals if ((data[idx][1] >= data[i][0]) or (data[i][0] == data[idx][1] + 1)): # Merge the previous and the # current interval data[idx][1] = max(data[idx][1], data[i][1]) else: idx += 1 data[idx][1] = data[i][1] data[idx][0] = data[i][0] # Stores the required sum Sum = 0 # Loop to calculate the sum of all # the remaining merged intervals for i in range(idx+1): # Add sum of integers # in current range Sum += sumInRange(data[i][0], data[i][1]) # Return the total Sum return Sum # Driver Code if __name__ == "__main__": vec = [[-12, 15], [3, 9], [-5, -2], [20, 25], [16, 20]] print(calcSum(vec, len(vec))) # This code is contributed by ukasp.
Javascript
<script>
// JavaScript code for the above approach
// Function to find the sum of all
// integers numbers in range [L, R]
function sumInRange(L, R) {
let Sum = ((R - L + 1) / 2)
* (2 * L + (R - L));
return Sum;
}
// Function to find sum of all integers
// that lie in any of the given ranges
function calcSum(data, n) {
// Sort intervals in increasing order
// according to their first element
data.sort(function (a, b) { return a.first - b.first })
// Merging the overlapping intervals
let i, idx = 0;
// Loop to iterate through the array
for (i = 1; i < n; i++) {
// If current interval overlaps
// with the previous intervals
if ((data[idx].second >=
data[i].first)
|| (data[i].first ==
data[idx].second + 1)) {
// Merge the previous and the
// current interval
data[idx].second
= Math.max(data[idx].second,
data[i].second);
}
else {
idx++;
data[idx].second = data[i].second;
data[idx].first = data[i].first;
}
}
// Stores the required sum
let Sum = 0;
// Loop to calculate the sum of all
// the remaining merged intervals
for (i = 0; i <= idx; i++) {
// Add sum of integers
// in current range
Sum += sumInRange(data[i].first,
data[i].second);
}
// Return the total Sum
return Sum;
}
// Driver Code
let vec
= [{ first: -12, second: 15 },
{ first: 3, second: 9 },
{ first: -5, second: -2 },
{ first: 20, second: 25 },
{ first: 16, second: 20 }];
document.write(calcSum(vec, vec.length));
// This code is contributed by Potta Lokesh
</script>
Producción
247
Complejidad de tiempo : O(N*log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por akashjha2671 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA