Единичная длина закрытых интервалов

Question

Я работаю над программой, которая в некоторой степени сосредоточена на следующем:

Замкнутый интервал в реальной единице - это интервал [x, 1 + x].Для данного входного набора

X = {x1, x2, ..., Xn}, x1

Мне не нужен код, но алгоритм для правильной настройки моей программы прекрасно подойдет

Спасибо

Answer 1

Ваши баллы отсортированы в порядке возрастания.Мы можем решить это жадным подходом.Начать первый интервал с x1.Затем установите начало второго интервала с первыми точками из первого интервала.И так далее.

Answer 2

Жадный: Временная сложность O (n), maximun. Как х1 <...

Answer 3

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