Покрытие точек отрезками

Ввод: список точек на прямой.

список точек напрямой

Вывод: Минимальное количество отрезков единичной длинны, с помощью которых можно покрыть все эти точки.

Пример реализации #1. В этом примере мы покрыли все точки 4-мя отрезками, что является не оптимальным решением:

Пример # 2 правильная реализации покрытия:

Так для того, что бы покрыть точки минимальным количество отрезков, необходимо:

  1. Отсортировать все точки в порядке возрастания.
  2. Начало первого отрезка равно самой координате первой точки, длинна отрезка по условию = 1
  3. Находим первую точку координата которой, больше координаты конца отрезка, это будет начало второго отрезка
def sections(coordinates):
    lines_coordinate = []
    points = sorted(coordinates)
    count_points = len(points)
    i = 0
    while i < count_points:
        start = points[i]
        stop = points[i] + 1
        lines_coordinate.append([start, stop])
        i += 1
        while i < count_points and points[i] <= stop:
            i += 1
    return lines_coordinate

lst = [0.5, 2, 1, 3.5, 10, 0.7, 1.2] # >>> sorted [0.5, 0.7, 1, 1.2, 2, 3.5, 10]
print(sections(lst))
# >>> [[0.5, 1.5], [2, 3], [3.5, 4.5], [10, 11]]