Menu Close

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

   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,

   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

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.”

John von Neumann.

Una solución de “Suma de intervalos

  1. Enrique Zubiría
    import Data.List
     
    sumaIntervalos :: [(Int, Int)] -> Int
    sumaIntervalos is = sum (map longitudIntervalo (reduceIntervalos is))
      where longitudIntervalo (a, b) = b - a
     
    reduceIntervalos :: [(Int, Int)] -> [(Int, Int)]
    reduceIntervalos is = aux $ sort is
      where aux []  = []
            aux [i] = [i]
            aux ((x1, x2):is)
              | y1 <= x2  = aux ([(x1, max y2 x2)] ++ tail is)
              | otherwise = (x1, x2) : aux is
              where (y1, y2) = head is

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.