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

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

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

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

Данные для выполнения этого задания находятся в файле электронной таблицы.

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

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

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

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

Ваш ответ: