Задача 6790. Источник: Поляков. Задание КИМ 26
(ЕГЭ-2023) Входной файл содержит сведения о заявках на проведение занятий в конференц-зале. В каждой заявке указаны время начала и время окончания мероприятия (в минутах от начала суток). Если время начала одного мероприятия меньше времени окончания другого, то провести можно только одно из них. Если время окончания одного мероприятия совпадает с временем начала другого, то провести можно оба. Определите максимальное количество мероприятий, которое можно провести в конференц-зале и самое позднее время окончания последнего мероприятия.
Входные данные представлены в файле 26-128.txt следующим образом. Первая строка входного файла содержит натуральное число N (1 ≤ N ≤ 1000) – количество заявок на проведение мероприятий. Следующие N строк содержат пары чисел, обозначающих время начала и время окончания мероприятий. Каждое из чисел натуральное, не превосходящее 1440.
Запишите в ответе два числа: максимальное количество мероприятий, которое можно провести в конференц-зале и самое позднее время окончания последнего мероприятия (в минутах от начала суток).
Пример входного файла:
5
10 150
100 110
131 170
131 180
120 130
При таких исходных данных можно провести максимум три мероприятия, например, по заявкам 2, 3 и 5. Конференц-зал освободится самое позднее на 180-й минуте, если состоятся мероприятия по заявкам 2, 4, 5. Ответ: 3 180.
Решение
Внешне задача выглядит простой, но в реальности имеет подводные камни. В первую очередь, это касается сортировки. Сортировать нужно не по времени начала занятий, а по времени окончания, т.к. рано начинающееся занятие может поздно заканчиваться, не давая провести иные мероприятия, а рано заканчивающееся занятие как раз позволит провести еще что-то. Сортировка по времени начала значения не имеет, т.к. если есть возможность провести несколько занятий с одинаковым временем окончания, безразлично, какое из них будет учтено. Вторым подводным камнем является максимальное время окончания последнего мероприятия. Для его поиска в переменной min_start будем фиксировать время окончания предпоследнего выбранного занятия. Если какое-то мероприятие может быть проведено вместо последнего (с минимальным временем окончания), время его окончания фиксируем в переменной max (mx).
Python
f = open('26-128.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]
if min_start <= i[0]:
mx = i[1]
print(k, mx)
PascalABC
var
n, k, min_start, finish, max, min, i, j, t: Integer;
a: array [1..991, 1..2] of Integer;
f: TEXT;
begin
Assign(f, '26-128.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];
end;
if min_start <= a[i, 1] then
max := a[i, 2]
end;
Writeln(k, ' ', max);
end.
C++
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("26-128.txt");
int n;
f >> n;
int a[991][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];
}
if (min_start <= a[i][0])
max = a[i][1];
}
cout << k << " " << max << endl;
}
Ответ
16 1345