Трансконтинентальная автотрасса представляет собой дорогу, на которой расположены 100 населённых пунктов, пронумерованных числами от 1 до 100. Как выбрать компанию чтобы они смогли произвести ремонт всей дороги целиком, то есть объединение участков?

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

Номер компании Начало участка Конец участка

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

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