По заданному набору интервалов найдите минимальное количество точек, которые необходимо разместить, чтобы в каждом интервале была точка

Question

Предположим, вам дан набор интервалов, время начала каждого интервала которого равно s, индекс i, и время окончания f, индекс i.Найдите минимальное количество точек, которые нужно поместить, чтобы каждый интервал имел точку.

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

Спасибо

Answer 1

1. Удалите все интервалы, которые полностью содержат меньший интервал.Вы можете сделать это, потому что, если меньший интервал удовлетворен, то больший интервал также должен быть удовлетворен.
2. Сортировка интервалов по s_i.
3. Начиная с первого интервала: поместите точку в f_i,Это будет соответствовать первому интервалу и любым интервалам, которые его перекрывают.
4. Продолжить в отсортированном порядке до следующего интервала, который еще не содержит точку, и поместить точку в f_i.
5. Повтор,

Answer 2

1. Сортировка интервалов в порядке убывания верхней границы.
2. Инициализировать переменную most_recent_placed до -inf (что-то меньше, чем все нижние границы интервала).
3. Сканирование интервалов в отсортированном порядке. Для данного интервала [a, b], если most_recent_placed < a, тогда установите точку на b и установите most_recent_placed на b.

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

Answer 3

На этот вопрос нужен ответ с кодом.Вот реализация Python алгоритма, который упоминает пользователь 612112, что немного лучше, чем в принятом ответе:

1. Инициализация пустого списка точек вывода
2. Сортировка диапазоновпо конечной точке и обработайте их в порядке конечной точки
3. Для каждого диапазона, если последняя выходная точка меньше начала диапазона, добавьте конечную точку диапазона к выходному набору

Обратите внимание, что вам не требуется никакой предварительной обработки для удаления избыточных диапазонов, и вам не нужна сортировка для различения нескольких диапазонов с одной и той же конечной точкой.

# given some inclusive ranges
ranges=[(1,5),(2,4),(4,6),(3,7),(5,9),(6,6)]

# sort by the end points
ranges.sort(key=lambda p:p[1])

#generate required points
out=[]
last = None
for r in ranges:
    if last == None or last < r[0]:
        last = r[1]
        out.append(last)

#print answer
print(out)

Answer 4

Сначала отсортируйте интервалы в порядке возрастания начальной точки.поставить точку на наименьшем фи.если следующий интервал, имеющий время окончания f (i + 1), имеет эту точку, то предыдущая точка покрывает f (i + 1), в противном случае ставим новую точку на f (i + 1).Итерация процедуры