Всем привет!
Сегодня хочу показать решение интересной 27-ой задачки с сайта К.Полякова!
(№ 5177) (99 баллов) Городская администрация устроила конкурс на украшение центра города. Центр города представляет из себя длинную улицу, на которой слева расположены различные магазины, модные бутики и рестораны, а справа – белая стена. Началом центральной улицы считается «нулевой метр». Для украшения они придумали разукрасить белую стену в центре. В итоге конкурса они выбрали N лучших участников. Каждый из них сообщил, на каком участке улицы он готов реализовать свою работу. Определите, какое наибольшее количество картин возможно разместить на стене так, чтобы они не пересекались.
Входные данные. Даны два входных файла (файл A и файл B), содержит в первой строке число N (1 ≤ N ≤ 100 000). Каждая из следующих N строк содержит два натуральных числа S и F (1 ≤ S < F ≤ 1 000 000) – границы участка, на котором очередной участник хочет разместить свою работу.
Пример входного файла:
6
1 3
4 6
4 5
10 11
7 9
7 13
Для этих данных администрация может выбрать картины первого (участок 1–3), второго (участок 4–6), четвертого (участок 10–11) и пятого участника (участок 7–9). Ответ: 4.
В ответе укажите два числа: сначала наибольшее количество картин для файла А, затем для файла B.
Мое решение:
1) Для начала считаем границы наших участков, далее добавим их в список.
2) После уберем из списка повторяющиеся участки с помощью функции set().
3) Так как у нас список кортежей, сортировать список будем вот таким образом:
a.sort(key = lambda a: a[-1])
То есть по возрастанию правой границы участка.
4) Создадим список buf. Туда будем добавлять удовлетворяющие условию участки!
5) Пройдемся по нашему списку, будем смотреть, если границ первого участка нет во втором участке, то добавляем два участка в наш список buf и выходим из цикла, предварительно запомним индекс следующего элемента, до которого мы еще не добрались.
6) Еще раз проходимся по нашему списку, но у же от i + 2 до len(a). Смотрим, если границы последнего добавленного участка не находятся в проверяемом участке, то добавляем этот участок. В конце просто выводим количество кортежей в списке buf с помощью len().
#егэ2022 #егэинформатика #программирование #python
