>для тебя

совсем не врубаешься

Высокая нагрузка

Автор решения: Дмитрий Терров. Задачу решили 14% участников

Вам дана история сессий на некотором вымышленном сервисе. Каждая сессия характеризуется временем начала и временем окончания si и fi, для удобства все эти значения различны.

Найдите такой момент времени t, когда было активно наибольшее количество сессий. Если таких моментов несколько, то выведите самый ранний из них. Ограничение времени: 1 с, ограничение памяти: 256 МБ.

Формат ввода
В первой строке входных данных записано целое число n (1 ≤ n ≤ 1000). Далее в n строках записано через пробел по два целых числа si и fi (0 ≤ si < fi ≤ 1 000 000 000).

Формат вывода
Выведите искомый момент времени t.

Решение


Простой, но не самый эффективный алгоритм — пройтись по всем сессиям и каждую сравнить с остальными, посчитав количество пересечений и найдя максимальное значение. Сложность этого алгоритма — O(N x N).

Но есть более оптимальный алгоритм. Для начала преобразуем список всех сессий в список событий двух типов — начало сессии и окончание сессии. Отсортируем эти события. Теперь, проходя по ним, мы будем прибавлять единицу к количеству одновременно активных сессий, если событие — это начало сессии и вычитать, если событие — окончание сессии. Сложность такого алгоритма — O(N x log N).

n = int(input()) sessions = [] for _ in range(n): x, y = map(int, input().split()) sessions.append((x, y)) events = [] for start, end in sessions: events.append((start, 1)) events.append((end, -1)) events.sort() max_number = min_time = cur_number = 0 for cur_time, operation in events: cur_number = cur_number + operation if cur_number > max_number: max_number = cur_number min_time = cur_time print(min_time)

Бля, отступы

Короче, ща ссылку кину

Ну так вот

Я хотел сказать, что могу это в одну строку решить

https://m.habr.com/ru/company/yandex/blog/488682/ высокая нагрузка

Следующую кста тоже

Изя

помойму тут больше алгоритмы нежели знание питона

И то, и то

Без знания питона, будет сложно решить некоторые задачи максимально производительно и компактно

Кста

Задачу про сжатые строки

Все

Изи

Language:

py3

Source:

print(sum([int(i) for i in "#" if not i.isalpha()]))

Errors:

Traceback (most recent call last):
  File "source_file.py", line 1, in <module>
    print(sum([int(i) for i in "#" if not i.isalpha()]))
  File "source_file.py", line 1, in <listcomp>
    print(sum([int(i) for i in "#" if not i.isalpha()]))
ValueError: invalid literal for int() with base 10: '#'

Жижа