Задача 6891. Источник: Поляков. Задание КИМ 27
(Г. Шапошников) Заявки на прием у начальника поступают в виде времени начала и конца планируемого приема. Будем считать, что приемы начинаются и заканчиваются в начале заданной минуты. Прием может быть проведен в том случае, если нет ни одного другого приема, который бы занимал хотя бы единицу времени, находящуюся в диапазоне времени проведения данного приема. По заданному списку заявок определите, сколько приемов удастся провести, при условии, что все заявки поступают в том порядке, в котором они представлены во входных файлах.
Входные данные. Даны два входных файла (файл A и файл B), каждый из которых в первой строке содержит натуральное число N (N ≤ 1000000) – количество заявок. Каждая из следующих N строк содержит два числа, X и Y (1 ≤ X < Y ≤ 100000000 и Y-X ≥ 10000), разделенные пробелом – время начала и время окончания планируемого приёма.
Пример входного файла:
7
100000 500000
490000 700000
500000 700000
10000 50000
60000 80000
50000 90000
710000 900000
При таких исходных данных будет проведено пять приёмов: первый, третий, четвертый, пятый и седьмой. Ответ: 5.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
Решение
Создадим массив/список/вектор, куда будем добавлять информацию о мероприятиях, которые возможно провести без пересечения с другими. Эти записи будут отсортированы. Последовательно обрабатываем исходные данные. Если очередное мероприятие заканчивается раньше начала самого первого, то добавляем это мероприятие в начало. Если мероприятие начинается позже окончания последнего, добавляем его в конец. В ином случае ищем можем ли мы вставить это мероприятие между какими-то двумя. Если это возможно, вставляем. Размер получившегося набора данных будет ответом на данную задачу.
Python
f = open("27-179b.txt")
n = f.readline()
a = []
for i in f:
x, y = map(int, i.split())
if len(a) == 0 or a[0][0] >= y:
a.insert(0, [x, y])
elif a[-1][1] <= x:
a.append([x, y])
else:
j = 0
while j < len(a) and a[j][1] <= x:
j += 1
if a[j][0] >= y:
a.insert(j, [x, y])
print(len(a))
PascalABC
type
Data = record
x: Integer;
y: Integer;
end;
var
n, i, j: Integer;
d: Data;
a: array of data = new Data[0];
f: TEXT;
begin
Assign(f, '27-179b.txt');
Reset(f);
Readln(f, n);
for i := 1 to n do
begin
Readln(f, d.x, d.y);
if (a.Length = 0) or (a[0].x >= d.y) then
a := Arr(d) + a
else if a[a.Length - 1].y <= d.x then
a := a + Arr(d)
else
begin
j := 0;
while (j < a.Length) and (a[j].y <= d.x) do
j := j + 1;
if a[j].x >= d.y then
a := a[:j] + Arr(d) + a[j:];
end;
end;
Writeln(a.Length);
end.
C++
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
struct ddata
{
int x;
int y;
};
int main()
{
ifstream f;
f.open("27-179b.txt");
int n;
f >> n;
vector<ddata> a;
for (int i = 0; i < n; i++)
{
ddata d;
f >> d.x >> d.y;
if (a.size() == 0 || a[0].x >= d.y)
a.insert(a.begin(), d);
else if (a[a.size() - 1].y <= d.x)
a.push_back(d);
else
{
int j = 0;
while (j < a.size() && a[j].y <= d.x)
j++;
if (a[j].x >= d.y)
a.insert(a.begin() + j, d);
}
}
cout << a.size() << endl;
}
Ответ
2 65