|
|
| (не показано 17 промежуточных версий 2 участников) |
| Строка 1: |
Строка 1: |
| − | Пусть все наши N отрезков представлены парами {left, id}, {right, id}. Где left - координата левого конца, right - координата правого конца, id - "номер" нашего отрезка.<br />
| + | <latex> |
| − | Так же, очевидно, что нам нужно как-то отмечать уже покрытые отрезки. Для этого заведем булевый массив flags[1..N], который изначально содержит все значения false.<br />
| + | Дано $N$ отрезков на прямой. Требуется покрыть их наименьшим числом точек, т.е. найти наименьшее множество точек такое, что каждому отрезку принадлежит хотя бы она точка. Предложить эффективный жадный алгоритм, оценить сложность. |
| − | Так же заведем LIFO очередь для хранения рассматриваемых в данный момент вершин. <br />
| + | </latex> |
| − | И массив для хранения ответов.<br />
| + | |
| − | Все пары наших отрезков {left, id}, {right, id} будут храниться в массиве.<br />
| + | |
| − | Отсортируем его по возрастанию координат отрезков. При чем, если у нас встречается "правая" и "левая" часть с одинаковой координатой, сначала в отсортированном массиве пойдет "левая", потом "правая". <br />
| + | |
| − | Данная операция займет минимум O(N*Log(N)) - если значение N неизвестно, или O(N)- если значение N известно.<br />
| + | |
| | | | |
| − | Начинаем обход нашего массива:<br />
| + | [[Категория:Решенные задачи]] |
| − | :Если мы встретили левый конец отрезка -> добавляем его в LIFO очередь.<br />
| + | [[Категория:Теоретические задачи]] |
| − | :Если мы встретили правый конец:<br />
| + | |
| − | ::Если в нашем массиве flags отрезок с этим id помечен как покрытый, ничего не делаем, пропускаем эту запись.<br />
| + | |
| − | ::Если в нашем массиве flags отрезок с этим id помечен как непокрытый, то добавляем координату его правого конца в ответ. Очевидно, что в нашей LIFO есть только "левые" части отрезков -> все они покрылись только что добавленной в ответ точкой. Поэтому, мы просто выталкиваем все "левые" концы из очереди, помечая их отрезки как покрытые. <br />
| + | |
| − | | + | |
| − | И так до самого конца массива. <br />
| + | |
| − | | + | |
| − | Т.к. мы просматриваем все элементы массива. Всего записей в массиве 2N. А так же тратим время на заталкивание/выталкивание из нашей LIFO очереди. В худшем случае в нее можно затолкать N элементов и N вытолкнуть(левых частей N штук), следовательно, времени на работу со стеком потратиться не более 2N. Поэтому количество операций не превосходит 4N. <br />
| + | |
| − | Следовательно, мы имеем сложность O(N) на обход.<br />
| + | |
| − | | + | |
| − | Таким образом, алгоритм будет работать или O(NlogN) или O(N) в зависимости от того, какая сортировка будет применена к массиву.<br />
| + | |
| − | [[Категория:На проверку]] | + | |