Suma de intervalos
Los intervalos se pueden representar por pares de enteros (a,b) con a < b. Los elementos del intervalo (2,5) son 2, 3, 4 y 5; por tanto, su longitud es 4. Para calcular la suma de los longitudes de una lista de intervalos hay que tener en cuenta que si hay intervalos superpuestos sus elementos deben de contarse sólo una vez. Por ejemplo, la suma de los intervalos de [(1,4),(7,10),(3,5)] es 7 ya que, como los intervalos (1,4) y (3,5) se solapan, los podemos ver como el intervalo (1,5) que tiene una longitud de 4.
Definir la función
|
1 |
sumaIntervalos :: [(Int, Int)] -> Int |
tal que (sumaIntervalos xs) es la suma de las longitudes de los intervalos de xs contando los superpuestos sólo una vez. Por ejemplo,
|
1 2 3 4 5 6 7 |
sumaIntervalos [(1, 5)] == 4 sumaIntervalos [(0,1), (-1,0)] == 2 sumaIntervalos [(0,1), (0,2), (1,2)] == 2 sumaIntervalos [(1, 5), (6, 10)] == 8 sumaIntervalos [(1, 5), (5, 10)] == 9 sumaIntervalos [(1, 5), (1, 5)] == 4 sumaIntervalos [(1, 4), (7, 10), (3, 5)] == 7 |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
import Data.List (nub, sort) -- 1ª solución sumaIntervalos :: [(Int, Int)] -> Int sumaIntervalos = aux . sort where aux [] = 0 aux [(a,b)] = b - a aux ((a,b):(c,d):xs) | b < c = b - a + aux ((c,d):xs) | otherwise = aux ((a,max b d):xs) -- 2ª solución sumaIntervalos2 :: [(Int, Int)] -> Int sumaIntervalos2 = length . nub . concatMap f where f (a, b) = [a..b - 1] |
Otras soluciones
- Se pueden escribir otras soluciones en los comentarios.
- El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>
Pensamiento
«Si la gente no cree que las matemáticas son simples, es sólo porque no se dan cuenta de lo complicada que es la vida.»
Un comentario