python - problems - dynamic programming steps

¿Algoritmo para encontrar el período más ocupado?

Question

Tengo algunos datos como este:

1: 2 - 10
2: 3 - 15
3: 4 - 9
4: 8 - 14
5: 7 - 13
6: 5 - 10
7: 11 - 15

Intentaré una representación para hacerlo más claro:

        1     2     3     4     5     6     7     8     9     10     11     12     13     14     15
1             |--------------------------------------X---------|
2                   |--------------------------------X--------------------------------------------|
3                         |--------------------------X---|
4                                                  |-X-------------------------------------|
5                                           |--------X------------------------------|
6                               |--------------------X----------|
7                                                                     |---------------------------|

Entonces, en el caso de ejemplo, 8-9 es el período crítico si se usa el segundo esquema porque todos los puntos están activos. ¿Cuál es una manera rápida y buena de resolver este problema en Python? Estoy pensando en usar programación dinámica, pero ¿hay otros enfoques que se sugieren?

Mi acercamiento hasta ahora:

Estaba pensando más desde una perspectiva en tiempo real. Entonces, cada vez que obtengo un nuevo punto, hago esto: Supongo que ya tengo 2-10 y que obtengo 3-15 luego escojo el máximo de inicio y mínimo de final, por lo que este caso es 3-10 e incremento el conteo de este intervalo a 2. Luego el tercer punto viene en 4-9 , elija el máximo que es 4 y el mínimo es 9 y actualice el valor 3-10 a 4-9 y actualice la cuenta a 3. Ahora, cuando aparece 8-14 , yo El comienzo de este intervalo es mayor que 4-9 y el final de este intervalo es menor que 4-9 . En este caso, no es cierto, por lo que crearé un nuevo grupo 8-14 y pondré el recuento a 1. Este no es el algoritmo completo, pero debería dar una idea general de lo que estoy haciendo aquí. Veré si puedo dibujar el pseudocódigo.

Answer 1

Comenzaría pensando en la ocupada posición de un punto x como el número de activaciones a la izquierda de x, menos el número de desactivaciones a la izquierda de x. Ordenaría las activaciones y desactivaciones por el momento en que ocurren (en tiempo O (nlog (n))). Luego puede recorrer la lista, rastrear el número activo (y), incrementando y disminuyendo ese número con activaciones y desactivaciones aprobadas. El período más ocupado serán los puntos en los que y está en su máximo. No puedo pensar en una solución que sea mejor que O (nlog (n)). La fuerza bruta sería O (n ^ 2).

Answer 2

Esto es lo que estaba pensando para el enfoque basado en bin, y adaptado para manejar agrega dinámicamente, básicamente lo que RK estaba diciendo, creo.

from collections import defaultdict
from operator import itemgetter

class BusyHour(object):
    def __init__(self):
        self.pairs = defaultdict(int)
    def add_period(self, period):
        start, end = period
        for current_period in range(start, end):
            pair_key = (current_period, current_period + 1) 
            self.pairs[pair_key] += 1
    def get_max(self):
        # sort, defaults to smallest to largest
        # --> items() returns (key, value) pairs
        # --> itemgetter gets the given index of the first argument given to sorted
        return max(self.pairs.items(), key=itemgetter(1))


if __name__ == ''__main__'':
    periods = [(2, 10), (3, 15), (4, 9), (8, 14), (7, 13), (5, 10), (11, 15)]
    bh = BusyHour()
    for period in periods:
        bh.add_period(period)
    print bh.get_max()

Actualizado : solo ordene en llamada a get_max, y use defaultdict (int).

Answer 3

No estoy seguro si entiendo tu pregunta. Si está intentando encontrar el "intervalo" más común, puede resumirlos por intervalo. De esta manera tienes 12 cubos para el ejemplo anterior. Para cada uso, agregaría 1 a cada uno de los compartimientos utilizados en ese uso en particular, y al final, encontrará el valor máximo en todos los compartimientos. Aquí, eso sería 6 para el intervalo 8-9.

Answer 4

Pensé que quizás podrías usar un set () para esto, y funcionaría si estuvieras seguro de que todos los períodos se cruzan en al menos un punto.

Sin embargo, esto no funciona tan pronto como un período no se interseca. Es posible que pueda agregar lógica adicional para cubrir esto, así que publicaré lo que estaba pensando:

>>> periods = [(2, 10), (3, 15), (4, 9), (8, 14), (7, 13), (5, 10),]
>>> intersected = None
>>> for first, second in periods:
...     if not intersected:
...         intersected = set(range(first, second + 1))
...     else:
...         intersected = intersected.intersection(set(range(first, second + 1)))
...
>>> intersected
set([8, 9])

Nota: esto no incluye el periodo 11-15. Probablemente lo mejor sea crear pares de contenedores como lo menciona RK

Answer 5

        1     2     3     4     5     6     7     8     9     10     11     12     13     14     15
1             |--------------------------------------X---------|
2                   |--------------------------------X--------------------------------------------|
3                         |--------------------------X---|
4                                                  |-X-------------------------------------|
5                                           |--------X------------------------------|
6                               |--------------------X----------|
7                                                                     |---------------------------|

             +1    +1     +1   +1           +1     +1    -1    -2     +1           -1     -1     -2
              1     2     3     4           5       6    5      3     4             3      2      0
                                                     ^^^^

¿Consíguelo?

Así que necesitas transformar esto:

1: 2 - 10
2: 3 - 15
3: 4 - 9
4: 8 - 14
5: 7 - 13
6: 5 - 10
7: 11 - 15

dentro:

[(2,+), (3,+), (4,+), (5,+), (7,+), (8,+), (9,-), (10,-), (10,-), (11,+), (13,-), (14,-), (15,-), (15,-)]

y luego simplemente recorres, contando cuando ves un + y contando -. El intervalo más ocupado será cuando el recuento sea máximo.

Así en el código:

intervals = [(2, 10), (3, 15), (4, 9), (8, 14), (7, 13), (5, 10), (11, 15)]
intqueue = sorted([(x[0], +1) for x in intervals] + [(x[1], -1) for x in intervals])
rsum = [(0,0)]
for x in intqueue: 
    rsum.append((x[0], rsum[-1][1] + x[1]))
busiest_start = max(rsum, key=lambda x: x[1])
# busiest_end = the next element in rsum after busiest_start 

# instead of using lambda, alternatively you can do:
#     def second_element(x):
#         return x[1]
#     busiest_start = max(rsum, key=second_element)
# or:
#     import operator
#     busiest_start = max(rsum, key=operator.itemgetter(1))

la complejidad del tiempo de ejecución es (n+n)*log(n+n)+n+n o O(n*log(n))

También es posible convertir esta idea en un algoritmo en línea si no tiene la lista completa de intervalos al inicio del programa, pero se garantiza que los intervalos entrantes nunca se programarán para un punto anterior. En lugar de ordenar, utilizará una cola de prioridad, cada vez que se produzca un intervalo, empujará dos elementos, el punto inicial y el punto final, cada uno con un +1 y un -1 respectivamente. Y luego se apaga, cuenta y hace un seguimiento de la hora pico.