Question

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

В первой строке входного файла находится натуральное число *N* (*N* ≤ 1000), обозначающее количество собраний. Каждая из следующих *N* строк содержит два натуральных числа: указанное в заявке время начала проведения (в минутах от начала суток, не превышает 1000) и время окончания (в минутах, не превышает 1400) собрания.Запишите в ответ два числа: максимальное количество собраний и время между началом первого мероприятия и окончанием последнего. **Типовой пример организации данных во входном файле:**510 150100 110120 130131 150131 180

Ответ:

Accepted Answer

Answer

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

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

Определите:
1. Максимальное количество собраний, которые можно провести без пересечений.
2. Время между началом первого мероприятия и окончанием последнего в оптимальном расписании.

Если способов выбрать последнее собрание несколько, выбрать нужно то, длительность которого больше.

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

**Пример входных данных:**
```
5
10 150
100 110
120 130
131 150
131 180
```

**Ожидаемый ответ:** `16 1008`

### РЕШЕНИЕ

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

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

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

**Шаг 3.** Удалим последнее выбранное собрание из расписания и найдём среди оставшихся совместимых с предпоследним собранием то, которое имеет максимальную длительность. Это станет новым последним собранием.

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

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

# Сортируем по времени окончания
meetings.sort(key=lambda x: x[1])

# Жадный выбор: начинаем с первого собрания
schedule = [meetings[0]]
last_end = meetings[0][1]
last_index = 0

# Добавляем совместимые собрания
for i in range(1, n):
    if last_end <= meetings[i][0]:
        schedule.append(meetings[i])
        last_end = meetings[i][1]
        last_index = i

# Сохраняем время окончания последнего выбранного собрания
final_end = schedule[-1][1]
final_duration = schedule[-1][1] - schedule[-1][0]

# Удаляем последнее собрание
schedule.pop()
prev_end = schedule[-1][1]

# Ищем среди оставшихся совместимых собраний
# то, которое имеет максимальную длительность
candidates = [
    m for m in meetings
    if m[0] >= prev_end and meetings.index(m) > last_index
]

if candidates:
    best = max(candidates, key=lambda x: x[1] - x[0])
    final_end = best[1]

print(len(schedule) + 1, final_end - schedule[0][0])
```

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

### ОТВЕТ

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