B. Вася, переехав из своего родного города, сильно скучает по старым друзьям. К сожалению, из-за маленькой квартиры
B. Вася, переехав из своего родного города, сильно скучает по старым друзьям. К сожалению, из-за маленькой квартиры Вася может принимать только одного друга одновременно. Каждый друг сообщает Васе два числа, A и B, указывающих на промежуток дней, в течение которого они могут приехать в гости. Приезд и отъезд каждого друга происходит в полдень. Каждый друг может приехать только один раз и оставаться у Васи несколько дней. Вася хотел бы определить даты приезда для каждого друга таким образом, чтобы общее количество дней, когда у него будет хотя бы один друг в гостях, было максимально возможным.
Schuka 21
Для решения данной задачи, Васе следует использовать алгоритм активностей. Этот алгоритм позволяет определить наибольшее количество активностей, которые могут происходить одновременно.Шаг 1: Сортировка промежутков по возрастанию дня начала.
Шаг 2: Выбор первого промежутка и добавление его в список выбранных промежутков.
Шаг 3: Для каждого промежутка следующего в списке:
- Если день начала промежутка больше чем день окончания последнего выбранного промежутка, добавляем его в список выбранных промежутков.
Шаг 4: Выводим список выбранных промежутков.
Теперь, давайте применим этот алгоритм к нашей задаче:
1. Сортировка промежутков:
У нас есть промежутки друзей A и B:
Промежуток A = [2, 5]
Промежуток B = [1, 6]
Отсортируем их в порядке возрастания дня начала.
Промежуток B = [1, 6]
Промежуток A = [2, 5]
2. Выбор первого промежутка:
Выберем первый промежуток B = [1, 6] и добавим его в список выбранных промежутков.
3. Перебор последующих промежутков:
Промежуток A = [2, 5]
День начала промежутка A (2) меньше, чем день окончания последнего выбранного промежутка B (6), поэтому пропускаем промежуток A и переходим к следующему.
4. Вывод списка выбранных промежутков:
Список выбранных промежутков: [B]
Таким образом, наибольшее количество дней, когда у Васи будет хотя бы один друг в гостях, равно 6 дням, что соответствует промежутку B [1, 6].