在某些约束条件下求可能的最大会议数的算法

Question

假设我想和一些朋友见面，他们会以时间间隔的形式向我发送他们的可用性。例如[1,4]表示朋友可以在第1、2、3和4天见我。我有一个我的朋友的所有时间间隔的列表，其中list[I]=一个朋友I的时间间隔。我的一个限制是我每天只能见到一个朋友。我如何着手编写一个算法来找到我能遇到的最大数量的朋友？在

Input是一个名为times
times = [(2,6), (2,20), (3,3), (5,6)] max_meetings(times) = 4
因为我们可以在第二天遇到朋友1，在第四天遇到朋友2，在第三天遇到朋友3，在第五天遇到朋友4。

下面是我的代码，它可以生成所有可能的n元组的会议时间，然后只检查哪一个符合约束。在

allPossibleSolutions = []
def helper(arr, spotsTaken, ind):
  if ind == len(arr):
    return
  for j in range(arr[ind][0], arr[ind][1]+1):
    if j not in spotsTaken:
      allPossibleSolutions.append(spotsTaken+[j])
      helper(arr, spotsTaken+[j], ind+1)

def max_meetings(times): 
  helper(times, [], 0)
  myMax = 0
  for sol in allPossibleSolutions:
    if len(sol) > myMax:
      myMax = len(sol)
  return myMax

ret = max_meetings([[2, 2], [4, 5], [4, 10], [5, 6], [5, 7], [6, 6]])
# ret = 6, correct answer for this. 

我试图找到最有效的解决方案，其中效率被定义为最佳的时间和空间复杂性。（如有必要，在空间上优化时间）

Answer 1

我认为字典是存储这些信息的好方法，关键字是日期，值是朋友数。所以你会得到这样一本字典：

{1: 4, 2: 3, 3: 9, 4: 2}

从这本字典我们可以看出，第一天有四个朋友，第二天有三个朋友，第三天有九个朋友，第四天有两个朋友。所以，赢家是第三天，因为它的价值最大。在

要构建这本字典，请将每个间隔扩展到其完整的天数列表中。然后，对于每一天，如果字典中没有该日期，则将其添加为1，否则增加其当前值。在