Участница:Lyapustinamaria/отрезок жадина

Материал из DISCOPAL
Перейти к: навигация, поиск

Заметим сначала, что можно рассматривать только те решения, в которых каждая из точек находится на правом конце какого-либо отрезка. Действительно, нетрудно понять, что любое решение, если оно не удовлетворяет этому свойству, можно привести к нему, сдвигая его точки вправо настолько, насколько это возможно.

StasFomin 18:05, 15 мая 2019 (MSK): В смысле до ближайшего правого конца от какого-то отрезка?

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

StasFomin 18:05, 15 мая 2019 (MSK): Плиз, пример данных, которых вы сортируете. А то не понятно, где тут жадность и вообще.

  • Заведём стек, в котором будут храниться номера отрезков, рассматриваемых в данный момент; изначально стек пуст.
  • Будем двигаться по точкам в отсортированном порядке.
  • Если текущая точка — левый конец, то просто добавляем номер её отрезка в стек.
  • Если же она является правым концом, то проверяем, не был ли покрыт этот отрезок (для этого можно просто завести массив булевых переменных).
    • Если он уже был покрыт, то ничего не делаем и переходим к следующей точке (забегая вперёд, мы утверждаем, что в этом случае в стеке текущего отрезка уже нет).
    • Если же он ещё не был покрыт, то мы добавляем текущую точку в ответ, и теперь мы хотим отметить для всех текущих отрезков, что они становятся покрытыми. Поскольку в стеке как раз хранятся номера непокрытых ещё отрезков, то будем доставать из стека по одному отрезку и отмечать, что он уже покрыт, пока стек полностью не опустеет. По окончании работы алгоритма все отрезки будут покрыты, и притом наименьшим числом точек (повторимся, здесь важно требование, что при равенстве координат сначала идут левые концы, и только затем правые).

Таким образом, весь алгоритм выполняется за O(N), не считая сортировки точек, а итоговая сложность алгоритма как раз равна O(NlogN).