Для организации ремонта дороги провели конкурс, в котором приняло участие 100 компаний. Какие компании выбрать?

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

Вам необходимо выбрать несколько компаний так, чтобы они смогли произвести ремонт всей дороги целиком, то есть объединение участков, которые могут отремонтировать выбранные компании, давало бы всю дорогу. Выбранные участки могут пересекаться. Например, допустимо выбрать две компании, первая из которых отремонтирует участок от города 1 до города 600, а вторая компания — от города 400 до города 1000 (если бы такие заявки были поданы компаниями). Или если первая компания может отремонтировать участок от города 1 до города 500, а вторая — от города 500 до города 1000, то эти две компании также смогут вместе отремонтировать всю дорогу.

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

Данные для выполнения этого задания находятся в файле электронной таблицы. Вы можете скачать файл в одном из двух форматов: Microsoft Excel (XLSX) или LibreOffice Calc (ODS).

Файл содержит три колонки. В колонке A указан номер компании от 1 до 100, в колонках B и C указаны концы участка, который может отремонтировать данная компания.

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

Для выполнения задания вы можете использовать электронные таблицы из офисного пакета или любые другие средства вашего компьютера.