Skip to main content
4 de 5
removeu 12 caracteres do conteúdo

Reduzir Tempo de execução Python3

To resolvendo um desafio aqui, que é, basicamente, ver quantos elementos de uma lista encaixam em TODOS os intervalos de uma matriz.

E minha solução foi essa:

def countSignals(frequencies, filterRanges):
    corretos = 0
    len_fR = len(filterRanges)
    for i in frequencies:
        for a in range(len_fR):
            if i in range(filterRanges[a][0], filterRanges[a][1] + 1):
                passou = True
                if passou and filterRanges[a] == filterRanges[-1]:
                    corretos+=1
            else:
                 break
    return corretos


if __name__ == '__main__':

    frequencies_count = int(input().strip())

    frequencies = []

    for _ in range(frequencies_count):
        frequencies_item = int(input().strip())
        frequencies.append(frequencies_item)

    filterRanges_rows = int(input().strip())
    filterRanges_columns = int(input().strip())

    filterRanges = []

    for _ in range(filterRanges_rows):
        filterRanges.append(list(map(int, input().rstrip().split())))

    result = countSignals(frequencies, filterRanges)

    print(result)

Como funciona a execução:

Recebo um número, que será equivalente à len(frequencies). Depois, recebo cada um dos elementos que irá compor a lista frequencies. Em seguida, recebo o valor de len(filterRanges). Depois recebo a dimensão de cada uma das listas que compõe filterRanges No final, recebo os valores de cada uma das listas.

Exemplo de input:

5 #-> len(frequencies)
20 #-> frequencies[0]
5 #-> frequencies[1]
6 #-> frequencies[2]
7 #-> frequencies[3]
12# -> frequencies[4]
3 #-> len(filterRanges), sendo que este é composto por listas
2 #-> tamanho das listas que compõe filterRanges
10 20 #-> filterRanges[0] = [10,20]
5 15 #-> filterRanges[1] = [5,15]
5 30 #-> filterRanges[2] = [5,30]

O código precisa contar quantos valores de frequencia estão no intervalo de TODAS as listas que compõe filterRanges.

Nesse caso, por exemplo, o retorno seria 1, pois apenas o numero 12 se encaixa em todos os intervalos.

Ele passou em 10 dos 15 testes, e os outros 5 deu timeout. alguém tem alguma sugestão para otimizar o código? O erro que deu foi "Terminated due to timeout", porque o codigo ficou executando por mais de 10 segundos (ele dá timeout qunado chega em 10). Como faço pra otimizar esse código?

EDIT APÓS SUGESTÕES:

def countSignals(frequencies, ranges):
    for i in range(len(ranges)):
       range_obj = range(ranges[i][0], ranges[i][1] + 1)
       ranges[i] = range_obj
    return sum(1 if all(f in r for r in ranges) else 0 for f in frequencies)


if __name__ == '__main__':

    frequencies_count = int(input().strip())

    frequencies = []

    for _ in range(frequencies_count):
        frequencies_item = int(input().strip())
        frequencies.append(frequencies_item)

    filterRanges_rows = int(input().strip())
    filterRanges_columns = int(input().strip())

    filterRanges = []

    for _ in range(filterRanges_rows):
        filterRanges.append(list(map(int, input().rstrip().split())))

    result = countSignals(frequencies, filterRanges)

    print(result)

Passei em 12/15 testes. Preciso otimizar mais... Não consigo alterar nada definido no método main, apenas consigo alterar a função countSignals.