[PYTHON] the smallest set of unit-length closed intervals

 

Given a set X1, X2,..., Xn of points on the real line, determine the smallest set of unit length closed intervals (e.g. the interval [1.25,2.25] includes all Xi such that 1,25 ≤ Xi ≤2.25) that contains all of the points. Give the most efficient algorithm you can to solve this problem, prove it is correct and analyze the time complexity.
실제 선에있는 점의 X1, X2, ..., Xn 집합이 주어지면 가장 작은 단위 길이 폐쇄 구간 집합을 결정합니다 (예 : 구간 [1.25,2.25]에는 1,25 ≤ Xi ≤2.25가되는 모든 Xi가 포함됩니다. ) 모든 점을 포함합니다. 이 문제를 해결할 수있는 가장 효율적인 알고리즘을 제공하고, 정확함을 증명하고, 시간 복잡성을 분석하십시오.

unit-length intervals의 수는 점 사이의 간격에 따라 1과 n 사이가 될 수 있다.
그리디 알고리즘으로 처음 간격을[x1, x1+1]으로[x1, x1+1] 사이에 있는 모든 점들을 제거한다.
그리고 다음 가장 왼쪽 점이xi이므로 다음 간격을 [xi,xi+1][xi, xi+1]로 설정한다. 이 구간에 해당되는 모든 점을 제거한 다음 나머지 점에서도 이 과정을 반복한다.
그렇기 때문에 이러한 알고리즘은 항상 greedygreedy 한 결과를 얻을 수 있으며 시간 복잡도는 O(n)이 된다.

 

<파이썬 코드>

def smallest_unit_length_intervals(points):
    points.sort()
    smallest_set = set()
    end_of_last_interval = float('-inf')
    for p in points:
        if end_of_last_interval <= p:
            interval = (p, p + 1)
            smallest_set.add(interval)
            end_of_last_interval = p + 1
    return smallest_set

points = input('점들을 입력하시오 : ').split()
points = [float(p) for p in points]

ans = smallest_unit_length_intervals(points)
print('A smallest-size set of unit-length intervals\n' 'that contain all of these points is', ans)

예를 들어 점들의0.1 1.2 2.3 4.4 일 때,

모든 점을 포함하는 smallest-size set of unit-length intervals는

{(0.1, 1.1), (1.2, 2.2), (2.3, 3.3), (4.4, 5.4)} 이 된다.