Задача 7185. Источник: Поляков. Задание КИМ 26
Входной файл содержит сведения о заявках на проведение занятий в конференц-зале. В каждой заявке указаны время начала и время окончания мероприятия (в минутах от начала суток). Если время проведения двух или более мероприятий пересекается, то провести можно не более одного из них. Между окончанием одного мероприятия и началом следующего необходим перерыв не менее 10 минут. Определите максимальное количество мероприятий, которое можно провести в конференц-зале, и максимальный перерыв между двумя последними мероприятиями.
Входные данные представлены в файле 26-142.txt следующим образом. В первой строке входного файла находится натуральное число N (1 ≤ N ≤ 1000) – количество заявок на проведение мероприятий. Следующие N строк содержат пары чисел, обозначающих время начала и время окончания мероприятий. Каждое из чисел натуральное, не превосходящее 1440.
Запишите в ответе два числа: максимальное количество мероприятий, которые можно провести в конференц-зале, и максимальный перерыв между последними мероприятиями (в минутах).
Пример входного файла:
5
10 150
100 110
131 170
131 180
120 130
При таких исходных данных можно провести максимум два мероприятия, например, по заявкам 2 и 3. Последнее мероприятие может начаться не позднее, чем в момент времени 131, так что максимальный перерыв составит 131 – 110 = 21 минуту. Ответ: 2 21.
Решение
Считываем данные в массив/список и сортируем их в порядке возрастания времени окончания мероприятия, т.к. рано заканчивающееся мероприятие может позволить провести другие. В переменной finish будем хранить минимальное время начала следующего мероприятия, в переменной min_start - минимальное время начала для последнего выбранного мероприятия, max - максимальный перерыв между последними двумя мероприятиями. Последовательно обрабатываем отсортированные данные. Если время начала рассматриваемого мероприятия больше или равно finish, то оно становится следующим проведенным (увеличиваем счетчик мероприятий и обновляем значения min_start, finish и max). Если рассматриваемое мероприятие может быть проведено вместо уже выбранного последнего (его время начала больше или равно min_start) и оно дает большую длительность перерыва, обновляем значение max. После обработки всех данных, выводим результат.
Python
f = open('26-142.txt')
n = int(f.readline())
a = [[int(y) for y in x.split()] for x in f]
a.sort(key=lambda x: x[1])
min_start = 0
finish = 0
mx = 0
k = 0
for i in a:
if finish <= i[0]:
k += 1
min_start = finish
finish = i[1] + 10
mx = i[0] - min_start + 10
if min_start <= i[0]:
mx = max(mx, i[0] - min_start + 10)
print(k, mx)
PascalABC
var
n, k, min_start, finish, max, min, i, j, t: Integer;
a: array [1..10000, 1..2] of Integer;
f: TEXT;
begin
Assign(f, '26-142.txt');
Reset(f);
Readln(f, n);
for i := 1 to n do
Readln(f, a[i, 1], a[i, 2]);
for i := 1 to n - 1 do
begin
min := i;
for j := i + 1 to n do
if a[j, 2] < a[min, 2] then
min := j;
if min <> i then
begin
t := a[i, 1];
a[i, 1] := a[min, 1];
a[min, 1] := t;
t := a[i, 2];
a[i, 2] := a[min, 2];
a[min, 2] := t;
end;
end;
min_start := 0;
finish := 0;
max := 0;
k := 0;
for i := 1 to n do
begin
if finish <= a[i, 1] then
begin
k := k + 1;
min_start := finish;
finish := a[i, 2] + 10;
max := a[i, 1] - min_start + 10;
end;
if (min_start <= a[i, 1]) and (a[i, 1] - min_start + 10 > max) then
max := a[i, 1] - min_start + 10;
end;
Writeln(k, ' ', max);
end.
C++
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("26-142.txt");
int n;
f >> n;
int a[10000][2];
for (int i = 0; i < n; i++)
f >> a[i][0] >> a[i][1];
for (int i = 0; i < n - 1; i++)
{
int min = i;
for (int j = i + 1; j < n; j++)
if (a[j][1] < a[min][1])
min = j;
if (min != i)
{
int t = a[i][0];
a[i][0] = a[min][0];
a[min][0] = t;
t = a[i][1];
a[i][1] = a[min][1];
a[min][1] = t;
}
}
int min_start = 0, finish = 0, max = 0, k = 0;
for (int i = 0; i < n; i++)
{
if (finish <= a[i][0])
{
k++;
min_start = finish;
finish = a[i][1] + 10;
max = a[i][0] - min_start + 10;
}
if (min_start <= a[i][0] && a[i][0] - min_start + 10 > max)
max = a[i][0] - min_start + 10;
}
cout << k << " " << max << endl;
}
Ответ
64 27