Задание EGEINF623F91: Сортировка, отбор и моделирование

Решение.

Сохраним приложенный текстовый файл под именем data.txt. Первая строка задаёт параметры задачи; её нельзя считать обычной записью данных. В программе нумерация элементов списка начинается с нуля, а номера из условия сохраняются без сдвига.

В файле 966 продуктов, номера совпадают с порядком строк после заголовка. У каждого продукта две разные величины: срок хранения и срок после вскрытия. Все 2N чисел различны, поэтому при выборе минимального числа ничья не возникает.

Для каждого числа сохраняем его значение, номер продукта и вид срока. Сортируем все эти записи по значению. Поддерживаем левую и правую границы ещё свободных мест рейтинга и множество уже размещённых продуктов.

При первом появлении продукта срок хранения отправляет его на левую свободную позицию, срок после вскрытия — на правую. Соответствующую границу сдвигаем. Второе число уже размещённого продукта пропускаем. Сохраняем номер и позицию при каждом действительном размещении, а не при каждом просмотренном числе.

Когда все продукты распределены, сохранённый номер относится к последнему размещённому продукту. Если его позиция с нуля равна p, выше стоят p продуктов, ниже — N − p − 1. Нужны более низкие места, поэтому берём N − p − 1. Последовательность действий совпадает с алгоритмом условия. Время O(N log N), память O(N).

Полная программа на Python:

with open("data.txt", encoding="utf-8-sig") as f:
    n = int(f.readline())
    values = []
    for number in range(1, n + 1):
        storage, opened = map(int, f.readline().split())
        values.append((storage, number, 0))
        values.append((opened, number, 1))
used = set()
left, right = 0, n - 1
for value, number, kind in sorted(values):
    if number in used:
        continue
    used.add(number)
    if kind == 0:
        position = left
        left += 1
    else:
        position = right
        right -= 1
    last_number, last_position = number, position
print(last_number, n - last_position - 1)

Проверка результата.

Последним размещён продукт 564: определяющее значение срока 97257, вид — после вскрытия. Его место в рейтинге при нумерации с единицы равно 522. Перед ним 521 продуктов, после него 444. Для данного условия выбираем второе из этих количеств.

Ответ: 564 444.