您好我有一個問題如下：
給定一組 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為每個呼叫重置。
uj5u.com熱心網友回復：
我認為遞回使實作過于復雜。雖然它仍然可行，但您必須傳入一堆額外的引數，這可能難以跟蹤。在我看來，迭代地實作這種方法要簡單得多。
此外，您的方法重復使用filter()and 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
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/461000.html