How to calculate the total seconds in a date range list by ignoring intersections of intervals in Python?

Question

I am trying to calculate the total time in a list of date ranges in Python, and if there is intersection between the intervals, it must merge to be calculated as if it were a new interval.

Interval 1:

intervalos = [
  {'inicio': datetime(2014, 11, 26, 10, 0, 0), 'fim': datetime(2014, 11, 26, 12, 0, 0)},
  {'inicio': datetime(2014, 11, 26, 11, 0, 0), 'fim': datetime(2014, 11, 26, 13, 0, 0)},
]
self.assertEqual(calcular_tempo(intervalos), 10800)

Interval 2:

intervalos = [
  {'inicio': datetime(2014, 11, 26, 10, 0, 0), 'fim': datetime(2014, 11, 26, 11, 0, 0)},
  {'inicio': datetime(2014, 11, 26, 10, 30, 0), 'fim': datetime(2014, 11, 26, 11, 30, 0)},
  {'inicio': datetime(2014, 11, 26, 12, 0, 0), 'fim': datetime(2014, 11, 26, 12, 30, 0)},
  {'inicio': datetime(2014, 11, 26, 9, 0, 0), 'fim': datetime(2014, 11, 26, 13, 0, 0)},
]
self.assertEqual(calcular_tempo(intervalos), 14400)

Interval 3:

intervalos = [
  {'inicio': datetime(2014, 11, 26, 10, 0, 0), 'fim': datetime(2014, 11, 26, 11, 0, 0)},
  {'inicio': datetime(2014, 11, 26, 10, 30, 0), 'fim': datetime(2014, 11, 26, 11, 30, 0)},
  {'inicio': datetime(2014, 11, 26, 12, 0, 0), 'fim': datetime(2014, 11, 26, 12, 30, 0)},
  {'inicio': datetime(2014, 11, 26, 12, 40, 0), 'fim': datetime(2014, 11, 26, 12, 50, 0)},
  {'inicio': datetime(2014, 11, 26, 5, 0, 0), 'fim': datetime(2014, 11, 26, 10, 1, 0)},
]
self.assertEqual(calcular_tempo(intervalos), 25860)

I created a method to perform the calculation, however the result is failing for some tests the code works but the logic is weak.

The method:

def calcular_tempo(objetos):    
    intervalos = []
    intervalos_add = []
    intervalos_del = []

    for objeto in objetos:
        if intervalos:
            for intervalo in intervalos:
                if intervalo['inicio'] < objeto['inicio'] < intervalo['fim']:
                    if objeto['fim'] > intervalo['fim']:
                       intervalos_del.append(intervalo)
                       intervalos_add.append({'inicio': intervalo['inicio'], 'fim': objeto['fim']})

                elif intervalo['fim'] > objeto['fim'] > intervalo['inicio']:
                    if objeto['inicio'] < intervalo['inicio']:
                        intervalos_del.append(intervalo)
                        intervalos_add.append({'inicio': objeto['inicio'], 'fim': intervalo['fim']})

                elif objeto['inicio'] < intervalo['inicio'] and objeto['fim'] > intervalo['fim']:
                    intervalos_del.append(intervalo)
                    intervalos_add.append(objeto)

                elif objeto['inicio'] != intervalo['inicio'] and objeto['fim'] != intervalo['fim']:
                    intervalos_add.append(objeto)
                else:
                    intervalos.append(objeto)

                for deletar in intervalos_del:
                    intervalos.remove(deletar)

                intervalos_sem_repeticoes = []
                for add in intervalos_add:
                    if add not in intervalos_sem_repeticoes:
                        intervalos_sem_repeticoes.append(add)

                intervalos = intervalos + intervalos_sem_repeticoes
                intervalos_add = []
                intervalos_del = []

            segundos_totais = 0

            for intervalo in intervalos:
                segundos_totais += (intervalo['fim'] - intervalo['inicio']).total_seconds()

            return segundos_totais

I believe that I am redundant in logic and leaving something to be desired in checking the intervals. I wasn’t going to put the method I did not influence, it would be interesting if they did this logic from scratch, because it must be simpler than the algorithm I did.

Answer 1

My suggestion is this::

1. Sort intervals by start date;
2. For each interval, if its beginning is less than the end of the last, merge the two:

Example (you passed your 3 tests):

def calcular_tempo(intervalos):
    intervalos = sorted(intervalos, key=lambda x: x['inicio'])
    ultimo = intervalos[0]
    for i in intervalos[1:]:
        if i['inicio'] < ultimo['fim']:
            ultimo['fim'] = max(ultimo['fim'], i['fim']) # Mescla os dois intervalos
            i['fim'] = i['inicio'] # Zera um deles
        else:
            ultimo = i
    return sum((i['fim'] - i['inicio']).total_seconds() for i in intervalos)

P.S. This example of code modifies the original ranges - if you need them after the method call, I suggest either clone them or change the above code accordingly.