Задача 7110. Источник: Поляков. Задание КИМ 26
(PRO100-ЕГЭ) Школьник Петя готовится к ЕГЭ по нескольким предметам в разных онлайн школах. У Пети есть расписание всех уроков. Он хочет посетить как можно больше уроков, при этом посещать уроки он хочет целиком. Ему не важно по какому предмету они будут, его интересует только количество посещённых уроков. При этом он хочет сделать селфи и выложить его в интернет сразу после первого просмотренного урока, и сделать он это хочет, как можно быстрее. Поэтому, если будет несколько способов выбрать посещённые уроки, он выберет тот способ, при котором конец первого урока будет раньше.
Входные данные представлены в файле 26-141.txt следующим образом. В первой строке входного файла находится натуральное число N (N ≤ 106) – общее количество уроков. В каждой из следующих N строка записаны два числа – время начала и время окончания урока. Если урок заканчивается в k-ю минуту, в ту же минуту Петя может начать просмотр следующего урока.
Запишите в ответе два числа: – максимальное количество уроков, которые сможет посетить Петя, и время селфи.
Пример входного файла:
4
3 8
1 6
6 9
5 20
При таких исходных данных Петя может посетить максимум два урока: [1, 6), [6, 9); время селфи – 6. Ответ: 2 6.
Решение
Считываем исходные данные в массив/список и сортируем в порядке возрастания времени окончания уроков, т.к. урок, который раньше заканчивается может позволить провести другие занятия. В переменной k будем подсчитывать количество подходящих уроков, а в переменной last - фиксировать время окончания последнего урока, который посетил Петя. Последовательно обрабатываем отсортированные данные. Если время начала очередного урока меньше или равно last, то увеличиваем счетчик уроков и обновляем значение last. Вторым числом в ответе является время окончания самого первого урока в отсортированных данных.
Python
f = open('26-141.txt')
n = int(f.readline())
a = [[int(y) for y in x.split()] for x in f]
a.sort(key=lambda x: x[1])
k = 0
last = 0
for i in a:
if i[0] >= last:
k += 1
last = i[1]
print(k, a[0][1])
PascalABC
var
n, k, last, min, i, j, t: Integer;
a: array [1..10000, 1..2] of Integer;
f: TEXT;
begin
Assign(f, '26-141.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;
k := 0;
last := 0;
for i := 1 to n do
if a[i, 1] >= last then
begin
k := k + 1;
last := a[i, 2];
end;
Writeln(k, ' ', a[1, 2]);
end.
C++
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("26-141.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 k = 0, last = 0;
for (int i = 0; i < n; i++)
if (a[i][0] >= last)
{
k++;
last = a[i][1];
}
cout << k << " " << a[0][1] << endl;
}
Ответ
93 116