Question

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

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

Ответ к примеру: 3 1.

Accepted Answer

Answer

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

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

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

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

**Пример входных данных:**
```
5
10 140
100 10
120 10
131 19
131 49
```

**Ожидаемый ответ:** 3 1

### РЕШЕНИЕ

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

Преобразуем каждое собрание в пару (время окончания, время начала) и сортируем по времени окончания. Затем жадно выбираем собрания: если текущее собрание начинается не раньше, чем заканчивается предыдущее выбранное, добавляем его в расписание.

```python
f = open('26_59776.txt')
n = int(f.readline())
meetings = []

for line in f:
    start, duration = map(int, line.split())
    end = start + duration
    meetings.append([end, start])

meetings.sort()

schedule = []
for i in range(n):
    if not schedule:
        schedule.append(meetings[i])
    elif meetings[i][1] >= schedule[-1][0]:
        schedule.append(meetings[i])

gap = schedule[-1][1] - schedule[-2][0]
print(len(schedule), gap)
```

Сложность: $O(n \log n)$ за счёт сортировки; основной цикл работает за $O(n)$.

### ОТВЕТ

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