#! /usr/bin/env python3 # OBI 2023 - Fase 2 # UPA - Solução O(N log N) com line sweep # Mateus Bezrutchka # Perceba que o problema é equivalente a, dados N intervalos na reta (o período # que cada ônibus ficará estacionado), calcular o número máximo de intervalos # que se intersectam -- podemos provar, via um argumento guloso, que se K é o # máximo de intervalos que se intersectam, então conseguimos estacionar todos os # ônibus usando K vagas, sempre alocando o ônibus que chega antes (intervalo mais # à esquerda) para qualquer vaga disponível. # Esse novo problema, dos intervalos que se intersectam, pode ser resolvido # com a técnica de "line sweep" -- criamos "eventos" em pontos da reta, indicando # que um intervalo começa (entra) ou termina (sai) nesse ponto (assim, temos # exatamente dois eventos por intervalo). Processamos esses eventos da esquerda # para a direita, mantendo um contador de quantos intervalos estão ativos # (intervalos que começaram mas não terminaram) na coordenada atual. MAXP = int(1e5 + 1) def read_int_list(): return [int(x) for x in input().split()] n = int(input()) eventos = [] for i in range(n): [chegada, partida] = read_int_list() eventos.append((chegada, 0)) # 0 indica que é o inicio do intervalo eventos.append((partida, 1)) # 1 indica que é o fim do intervalo eventos.sort() # ordena por coordenada intervalos_ativos = 0 max_intervalos_ativos = 0 for i in range(2 * n): if i > 0 and eventos[i - 1][0] != eventos[i][0]: # acabei de mudar de coordenada, preciso considerar a contagem anterior max_intervalos_ativos = max(max_intervalos_ativos, intervalos_ativos) if eventos[i][1] == 0: intervalos_ativos += 1 else: intervalos_ativos -= 1 # faltou considerar a ultima contagem max_intervalos_ativos = max(max_intervalos_ativos, intervalos_ativos) resp = 20 * max_intervalos_ativos print(resp)