Задача: Ремонт дороги

Трансконтинентальная автотрасса представляет собой дорогу, на которой расположены 100 населённых пунктов, пронумерованных числами от 1 до 100 (т.е. города разбивают дорогу на отдельные участки, дорога начинается в городе 1 и заканчивается в городе 100). Для организации ремонта дороги провели конкурс, в котором приняло участие 13 компаний. Каждая \(i\)-я компания предоставила заявку, согласно которой она может выполнить ремонт дороги от города номер \(a_i\) до города номер \(b_i\). Вот какие заявки были поданы компаниями:

Вам необходимо выбрать несколько компаний так, чтобы они смогли произвести ремонт всей дороги целиком, то есть объединение участков, которые могут отремонтировать выбранные компании, давало бы всю дорогу. Выбранные участки могут пересекаться. Например, допустимо выбрать две компании, первая из которых отремонтирует участок от города 1 до города 60, а вторая компания — от города 40 до города 100 (если бы такие заявки были бы поданы компаниями).

Для уменьшения бюрократических сложностей вам необходимо выбрать для проведения ремонта к̱ак можно меньше компаний.

Запишите номера компаний, которые вы выбираете для проведения ремонта дороги, в любом порядке. Чем меньше компаний вы выберете, тем больше баллов вы получите (при условии, что выбранный вами набор компаний удовлетворяет условию задачи).

Ваш ответ: