0

Mi problema es encontrar una manera eficiente de encajar un intervalo con un determinado peso en cualquier lugar dentro de dos límites y que no se superponga con los otros intervalos en el interior. El programa debe devolver todas las soluciones posibles.

Las propiedades son:

  • Todos los intervalos pueden tener pesos diferentes.
  • La lista dada de intervalos existentes no se solapa.
  • Los intervalos existentes están dentro de los límites.

Las restricciones son:

  • El nuevo intervalo tiene que estar dentro de los límites.
  • Los intervalos existentes no pueden ser modificados.
  • El nuevo intervalo no puede solapar los intervalos existentes.

De lo contrario, debe ser descartado ya que no puede ser insertado.

He encontrado alguna solución difícil que no funciona como se esperaba y no es nada eficiente, ¿conocéis alguna solución posible?

Os pongo un ejemplo simplificado con números.

Ejemplo del problema

4
  • 1
    Buen día, has publicado tu pregunta en el sitio de Stack Overflow en español, la pregunta está en un idioma que no es el oficial en este sitio y por lo tanto puede ser cerrada o votada negativamente. Te recomiendo que leas la sección ¿Cómo preguntar?. Puedes traducir tu pregunta o publicarla en el sitio de Stack Overflow en inglés. Commented el 21 jun. 2022 a las 9:34
  • Buen día, bienvenido(a) a la comunidad, te recomiendo hacer el recorrido de bienvenida y leer la sección ¿Cómo preguntar?. En este sitio no resolvemos tareas y/o proyectos. Para cada pregunta es necesario que agregues un ejemplo mínimo, completo y verificable para que podamos ayudarte. Commented el 21 jun. 2022 a las 9:35
  • ¿Qué tiene que ver el "peso" en todo esto? Lo mencionas pero no lo usas.
    – Candid Moe
    Commented el 21 jun. 2022 a las 10:03
  • Hola @CandidMoe, al final todos los intervalos tienen pesos, pero una vez colocados dentro de los limites, con saber el "inicio y final" es suficiente ya que el peso es una información redundante. Lo he expresado así porque el nuevo intervalo a añadir no tiene "inicio y final" como tal sino que tiene un peso, ¡espero haberlo aclarado!
    – Joan
    Commented el 21 jun. 2022 a las 10:10

1 respuesta 1

0

Me parece que esto funciona.

Primero, representamos la recta como una lista de valores 0 y 1, donde el cero representa una posición libre y el uno una ocupada. El ejemplo del problema, con intervalos [1,3] y [7,8] se representa así:

espacio = [0,1,1,1,0,0,0,1,1,0,0]

Un espacio libre es una o más celdas con ceros. Si aplica sum() sobre una rebanada de largo n y me da cero, sabre que todas las posiciones están vacias:

while True:
    largo = int(input("Largo del intervalo? "))
    start = 0
    while start + largo <= len(espacio):
        if sum(espacio[start:start+largo]) == 0:
            print(f"Posicion {start} disponible")
        start += 1

Aquí no estoy actualizando el espacio disponible, ya que el planteamiento exige mostrar todas las alternativas válidas.

Demo

espacio = [0,1,1,1,0,0,0,1,1,0,0]

while True:
    largo = int(input("Largo del intervalo? "))
    start = 0
    while start + largo < len(espacio):
        if sum(espacio[start:start+largo]) == 0:
            print(f"Posicion {start} disponible")
        start += 1

produce:

Largo del intervalo? 3
Posicion 4 disponible
Largo del intervalo? 1
Posicion 0 disponible
Posicion 4 disponible
Posicion 5 disponible
Posicion 6 disponible
Posicion 9 disponible
Posicion 10 disponible
Largo del intervalo? 

Alternativa

Una implementación alternativa es reemplazar sum() por any(). Esta última función retorna True si alguno de sus argumentos lo es. La ventaja es que en lugar de sumar toda la lista, any() retorna tan pronto encuentra el primer valor True.

Como en Python 0 es False y todo lo demás es True debería ser más rápida:

while True:
    largo = int(input("Largo del intervalo? "))
    start = 0
    while start + largo <= len(espacio):
        if not any(espacio[start:start+largo]):
            print(f"Posicion {start} disponible")
        start += 1
1
  • ¡Genial! Pese ser un problema simplificado, me ha servido de mucho el razonamiento que has hecho. ¡Muchas gracias!
    – Joan
    Commented el 22 jun. 2022 a las 14:22

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.