Программное решение задач ЕГЭ по информатике

Задача 6790. Источник: Поляков. Задание КИМ 26

Страница задачи 6790

(ЕГЭ-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

Отправить замечание по решению

Код по которому имеется замечание:

Ваш вариант кода:

Комментарий: