python - 寻找覆盖所有线段的最少点数

Question

您好，我有如下问题:

给定一组 n 个片段 {[a0, b0], [a1, b1], . . . , [an-1, bn-1]} 一条直线上有整数坐标，求最少m个点使得每段至少包含一个点。即，找到一组最小尺寸的整数 X，使得对于任何线段 [ai,bi] 都有一个点 x ∈ X 使得 ai ≤ x ≤ bi。

输入格式:输入的第一行包含段数n。以下n行中的每一行包含两个整数ai和bi(以空格分隔)定义第i段的端点坐标。

输出格式:第一行输出最少m个点，第二行输出m个点的整数坐标(以空格隔开)。您可以按任何顺序输出点。如果有很多这样的点集，你可以输出任何一组。 (不难看出，总存在一组最小尺寸的点，使得所有点的坐标都是整数。)

Sample 1:
Input: 3
1 3
2 5
3 6
Output: 1 3
Explanation:
In this sample, we have three segments: [1,3],[2,5],[3,6] (of length 2,3,3 respectively). All of them contain the point with coordinate 3: 1 ≤3 ≤3, 2 ≤3 ≤5, 3 ≤ 3 ≤ 6.
Sample 2:
Input: 4
4 7
1 3
2 5
5 6
Output: 2
3 6

解释:第二和第三段包含坐标为 3 的点，而第一和第四段包含坐标为 6 的点。所有四个段都不能被单个点覆盖，因为段 [1, 3] 和 [5, 6] 是不相交的。

解决方法:贪婪的选择是选择最小的右端点。然后删除包含该端点的所有段。 继续选择最小右端点并删除线段。

我遵循了解决方案。我找到了最小的右端点，删除了我代码中包含该端点的所有段。然后使用新的段列表再次执行函数(继续选择最小右端点并删除段 - 递归)但我坚持我的代码顺序并且无法使其工作。

list_time = [[4,7],[1,3],[2,5],[5,6]]

def check_inside_range(n, lst): #Function to check if a number is inside the range of start and end of a list
#for example 3 is in [3,5], 4 is not in [5,6], return False if in
    if lst[1]-n>=0 and n-lst[0]>=0:
        return False
    else:
        return True
def lay_chu_ki(list_time):

    list_time.sort(key = lambda x: x[1]) #Sort according to the end of each segments [1,3],[2,5],[5,6],[4,7]
    first_end = list_time[0][1] #Selecting the minimum right endpoint
    list_after_remove = list(filter(lambda x: check_inside_range(first_end, x),list_time))
    #Remove all segments that contains that endpoint

    lay_chu_ki(list_after_remove) #Keep doing the function again with new segments list
                                  #(Keep choosing minimum right endpoint and removing segments)

    return first_end #I don't know where to put this line.

print(lay_chu_ki(list_time))

如您所见，我已经完成了 3 个步骤:选择最小的右端点； 删除包含该端点的所有段； 继续选择最小右端点并删除线段，但它不会以某种方式起作用。我尝试先打印两个数字3和6(每次递归调用的返回结果)。我还尝试创建一个 count 变量来计算每个递归调用 (count +=1) 但它也不起作用，因为它重置了 count = 0 每次调用。

Answer 1

我认为递归使实现过于复杂。虽然它仍然可行，但您必须传递一堆额外的参数，这可能很难跟踪。在我看来，以迭代方式实现此方法要简单得多。

此外，您的方法重复使用 filter() 和 list()，每次执行时都需要线性时间(澄清一下，“线性”表示线性输入列表的大小)。在最坏的情况下，您会对列表中的每个元素执行该操作，这意味着您的原始实现的运行时间是二次的(假设您修复了代码中的现有问题)。这种方法通过单次遍历列表来避免这种情况:

def lay_chu_ki(list_time):
    list_time.sort(key=lambda x: x[1])
    idx = 0
    selected_points = []
    
    while idx != len(list_time):
        selected_point = list_time[idx][1]
        
        while idx != len(list_time) and list_time[idx][0] <= selected_point:
            idx += 1
        
        selected_points.append(selected_point)
    
    return selected_points
        

result = lay_chu_ki(list_time)
print(len(result))
print(' '.join(map(str, result)))

对于给定的列表，输出:

2
3 6