Дано число n и n интервалов l_i,r_i. Найдите любую перестановку p от 1 до n такую, что всех i от 1 до n выполняется l_i \leq pos_i \leq r_i, где pos_i - номер позиции в котором стоит число i в перестановке p. Например, если n=4,p_1=2,p_2=4,p_3=3, то pos_1=4,pos_2=1,pos_3=3,pos_4=2
Помогите решить эту задачу вообще нет идей.
Были примерно вот такие попытки: OdenR0 - Online C++0x Compiler & Debugging Tool - Ideone.com
для всех чисел я сохранила все индексы, в которых они могут быть расположены, и отсортировала их, чтобы сначала найти место для чисел, которые могут быть расположены в меньшем количестве мест, чем остальные
Мне пока в голову пришло грубое решение, которое, скорее всего, получит только 10 баллов. Нужно отсортировать интервалы по l, при равных l по r. Затем выбираете из каждого интервала минимальное число.
Почему это работает? Например, вам нужно выбрать интервал для pos= 1. Этим интервалом могут быть любые интервалы где l = 1. Из всех этих интервалов, лучше всего выбрать самый короткий, так как он не будет уменьшать ваш выбор для последующих pos.
Скорее всего более оптимальные решения будут строиться на этой идее
Отсортируйте отрезки по правой границе, идите слева направо и ставьте на позицию число с отрезка с минимальной правой границей и левой границей \leq позицию в которую сейчас ставите. Если наша текущая позиция < минимальной правой границы среди неиспользованных отрезков то ответ -1.
Почему это работает? (Строго доказывать не буду)
Пусть на данный момент мы выбираем из мультимножества отрезков X, пусть в этом множестве есть отрезок с минимальной правой границей r_{min}. На текущем шагу мы можем удалить любой из отрезков из мультимножества X.
Пусть текущая позиция на которой мы ставили отрезок была posi.
Введём функцию can(A, i) можно ли с мультимножества отрезков A заполнить все элементы начиная с i-го, функция возвращает 0 или 1.
Давай теперь рассмотрим два мультимножества Y и Z, Y - мультимножество полученное при удалении отрезка с r_{min}, а Z - мультимножества полученное при удалении отрезка с r_{del} и (min \neq del). Ну давай заметим что разница мультимножеств Y и Z в двух отрезках min и del, теперь заметим что так как r_{del} \geq r_{min} то для любого множества отрезков B в который входит отрезок min замена отрезка min на отрезка del не уменьшит значение функции can(B, posi + 1), ну и тут можно заметить что всегда выполняется can(Y, posi + 1) \geq can(Z, posi + 1). (Понимаю что не строго, но вроде теперь интуитивно понятней станет).
