Question

Входной файл содержит сведения о заявках на проведение занятий в конференц-⁠зале. В каждой заявке указаны время начала и время окончания мероприятия (в минутах от начала суток). Если время начала одного мероприятия меньше времени окончания другого, то провести можно только одно из них. Если время окончания одного мероприятия совпадает с временем начала другого, то провести можно оба. Определите какое максимальное количество мероприятий можно провести в конференц-⁠зале и каков при этом максимальный перерыв между двумя последними мероприятиями. Задание 26

**Входные данные.**В первой строке входного файла находится натуральное число *N* (*N* ≤ 1000) — количество заявок на проведение мероприятий.Следующие *N* строк содержат пары чисел, обозначающих время начала и время окончания мероприятий. Каждое из чисел натуральное, не превосходящее 1440.Запишите в ответе два числа: максимальное — количество мероприятий и самый длинный перерыв между двумя последними мероприятиями (в минутах).

Ответ:

Accepted Answer

Answer

### СТАТЕМЕНТ

Входной файл содержит сведения о заявках на проведение занятий в конференц-зале. В каждой заявке указаны время начала и время окончания мероприятия (в минутах от начала суток). Если время начала одного мероприятия меньше времени окончания другого, то провести можно только одно из них. Если время окончания одного мероприятия совпадает с временем начала другого, то провести можно оба.

Определите максимальное количество мероприятий, которые можно провести в конференц-зале, и найдите максимальный перерыв между двумя последними мероприятиями из выбранного набора.

**Входные данные.** В первой строке файла — натуральное число $N$ ($N \leq 1000$) — количество заявок. Следующие $N$ строк содержат пары чисел: время начала и время окончания мероприятия. Каждое число натурально и не превосходит 1440.

**Выходные данные.** Вывести два числа: максимальное количество мероприятий и самый длинный перерыв между двумя последними мероприятиями (в минутах).

### РЕШЕНИЕ

Идея решения: применить жадный алгоритм выбора мероприятий — отсортировать по времени окончания и выбирать те, которые не пересекаются с уже выбранными, затем найти максимальный перерыв между предпоследним и последним мероприятием, проверив все возможные замены последнего.

**Шаг 1.** Прочитаем данные и отсортируем мероприятия по времени окончания.

**Шаг 2.** Применим жадный алгоритм: начнём с первого мероприятия (с наименьшим временем окончания) и последовательно добавляем те мероприятия, время начала которых не меньше времени окончания последнего выбранного.

**Шаг 3.** После получения оптимального набора найдём перерыв между предпоследним и последним мероприятием. Затем переберём все оставшиеся мероприятия, которые могли бы заменить последнее, и вычислим перерыв для каждой такой замены.

**Шаг 4.** Выведем количество мероприятий и максимальный перерыв.

```python
f = open('26.txt')
f.readline()
a = []
for line in f:
    start, end = map(int, line.split())
    a.append([start, end])

a.sort(key=lambda x: x[1])

selected = [a[0]]
for i in range(1, len(a)):
    if a[i][0] >= selected[-1][1]:
        selected.append(a[i])

end_of_prelast = selected[-2][1]
max_gap = selected[-1][0] - end_of_prelast

for i in range(len(a)):
    if a[i][0] > selected[-1][0]:
        gap = a[i][0] - end_of_prelast
        max_gap = max(max_gap, gap)

print(len(selected), max_gap)
```

Сложность: $O(n \log n)$ (доминирует сортировка).

### ОТВЕТ

Задание №26ПрограммированиеЕГЭ по информатике