查找最少的积分数以覆盖所有细分市场

Question

嗨，我有一个问题如下：

给定一组N段{[A0，B0]，[A1，B1]，。 。 。 ，[an-1，bn-1]}在一条线上的整数坐标，找到最小数字m的点m，使每个段至少包含一个点。也就是说，找到一组最小尺寸的整数x，以便对于任何段[ai，bi]都有一个点x∈X，以便ai≤x≤bi。

输入格式：输入的第一行包含段的数字n。以下n行中的每条线都包含两个整数AI和BI（由空间隔开），以定义第i-th段的端点的坐标。

输出格式：在第一行上输出最小数字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，[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