调度算法，查找所有非重叠的固定长度区间

Question

我需要为我的管理应用程序实现一个算法，它可以告诉我何时以及向哪个用户分配任务。我已经实施了一个暴力解决方案，它似乎可以工作，但我想知道是否有更有效的方法来解决这个问题。为了简单起见，我已经重写了算法，使其能够在数字列表上操作（而不是在数据库查询等中操作）。下面我将尝试解释我的思路。

假设我们有3个用户可以被潜在地分配给该任务。

user_a_busy = [[1,2], [2,4], [5,6]]
user_b_busy = [[4,7], [7,8]]
user_c_busy = [[0,1], [1,5]]

列表中的每个元素表示用户在一天中不可用的时间段。因此，用户A在凌晨1点到2点之间忙碌，2点到4点之间也是如此。为了能够遍历用户并识别他们，我将上述列表以字典形式表示。

users_to_check = {'A':user_a_busy, 'B':user_b_busy, 'C':user_c_busy}

现在假设我们有一个需要1小时完成的任务，我们想要在午夜到上午10点之间每隔1小时检查一次（所以任务只能在整点开始）。下面是一个需要检查的每个时间段的列表。

task_intervals_to_check = [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [6, 7], [7, 8], [8, 9], [9, 10]]

这是一个检查两个区间是否重叠的函数：

def intervals_overlap(service, busy):
    if service[1] > busy[0] and service[0] < busy[1]:
        return True
    return False

所以现在这是一个循环，得出了可用的小时和可以分配给任务的用户的字典：

result = defaultdict(list)
for interval in task_intervals_to_check:
    for user, user_busy in users_to_check.iteritems():
        overlaps = False
        for busy_period in user_busy:
            if intervals_overlap(interval, busy_period):
                overlaps = True
                break
        if not overlaps:
            result[interval[0]].append(user)

对于持续时间为1小时的任务，结果如下：

{0: ['A', 'B'], 1: ['B'], 2: ['B'], 3: ['B'], 4: ['A'], 5: ['C'], 6: ['A', 'C'], 7: ['A', 'C'], 8: ['A', 'C', 'B'], 9: ['A', 'C', 'B']}

对于持续时间为2小时的任务，结果如下：

{0: ['B'], 1: ['B'], 2: ['B'], 5: ['C'], 6: ['A', 'C'], 7: ['A', 'C'], 8: ['A', 'C', 'B']}

这是预期的结果。下面是帮助我找到正确结果的图表：

那么我的问题是，有没有办法优化这个解决方案？这个解决方案是否可接受？

- Kesto

---

这是一个组合问题。你的代码可以在像这样的小例子上给出不错的答案，但在更复杂的问题上可能会给出非常低效的结果。你试过进行规模化测试了吗？结果可接受吗？如果不行，你可能需要研究快速的启发式方法，例如模拟退火。 - roganjosh

我不同意之前的评论，认为这是某种NP难度优化问题。正如OP所描述的那样，我们只需要找到单个任务可以被分配给哪个用户以及在什么时间，前提是我们已经有了他们的固定日程安排，不是吗？ - Ivan Gritsenko

@IvanGritsenko 这不是一个组合问题吗？选择一个员工来完成一项工作可能会基于其他员工的空闲时间使得可接受的解决方案变得不可能。如果你把它简化一下，多个员工之间可能存在平局，只有一个（如果有的话）能够导致所有工作都能完成的解决方案；贪心算法无法解决这个问题。 - roganjosh

@IvanGritsenko 就纯语义层面而言，我会让步，很公平。但从任何实际层面来看，这肯定是排课问题的变体。 - roganjosh

为了解释使用案例。具有任务分配权限的用户选择任务，然后选择日期，然后会得到一个任务可以分配的小时列表。当选择小时时，系统将随机选择一个用户（在可用用户中）并将任务分配给他。感谢大家的建议，我会研究并尝试弄清楚。 - Kesto

Answer 1

你可以尝试去掉最外层循环。假设你在ps, pe中检查期间的开始和结束（在示例中为0和10），任务持续时间为task_duration（在示例中为1或2）。假设一切都以整小时为单位，并且繁忙区间按时间排序。

result = defaultdict(list)
for user, user_busy in users_to_check.iteritems():
    for l_busy_per,r_busy_per in zip([[0, ps]] + user_busy, user_busy + [[pe, 0]]):
        avail_start = l_busy_per[1]
        avail_end = r_busy_per[0]
        for hit in range(avail_start, avail_end+1-task_duration):
            result[hit].append(user)

- Paul Panzer

Answer 2

我想在问题的表示上再加点内容。我认为只有起始时间的表示既足够又更自然。如果用户a在0-1、2-4和5-6期间都很忙，我建议采用这种表示方法：

a_busy = (0, 2, 3, 5)

这意味着每次在a_busy中，用户a都会忙碌一个时间单位。此外，这种分配时间段的方式更加自然。

task_times = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

我们甚至可以使用基本集合论为每个用户推导出解决方案。让user_busy成为起始时间的集合，其中用户在给定长度时无法被分配。此外，让slots_to_fill成为插槽的起始时间，这些插槽希望由用户填充，给定长度。然后，slots_to_fill和user_busy之间的差异是用户的最佳分配。以下是长度为2且用户a的示例：

user_busy = set([0, 1, 2, 3, 4, 5]) # Set where user cannot be assigned
slots_to_fill = set([0, 1, 2, 3, 4, 5, 6, 7, 8]) # Set where users shall be assigned
x = slots_to_fill - user_busy
print(x) # {6, 7, 8}

这个解决方案最困难的方面是从你的数据中构建集合。在这种对问题的自然表述中，解决方案很简单，可以分解并按用户进行处理。

from itertools import chain

user_busy = [[1,2], [2,4], [5,6]]
task_intervals_to_check = [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [6, 7], [7, 8], [8, 9], [9, 10]]
length = 2

# Convert original data to tuples of starting times
busy_start_time = tuple(chain.from_iterable(range(i, j) for i, j in user_busy))
slots_to_fill = tuple(chain.from_iterable(range(i, j) for i, j in task_intervals_to_check))

def assign(fillslots, not_avail, length):
    return filter(lambda x: all(x+i not in not_avail for i in range(length)) and x+length-1 <= max(fillslots), fillslots)

times = assign(slots_to_fill, busy_start_time, length)
print(list(times))

这将返回一个起始时间列表，用户可以被分配的时间更加方便处理，比列表更容易理解。结束时间可以通过将分配间隔的长度添加到开始时间来计算。

最后，我认为在运行时间方面进行优化没有太多好处，因为这个问题在计算上相对较便宜。 如果您想优化解决方案的质量，您首先必须定义一个目标。例如，这可以是像：在填充所有时间槽的同时最小化分配总数。但这不会增加问题的难度太多。 相关用户的限制将使问题变得更加困难，例如用户A和用户B不能在两小时内被分配，只有当用户B也被分配时才能分配用户C。

- Tristan

Answer 3

所以，我认为随着你的规模扩大，你将会实现更高级的公式，并且现在已经做了一个简单的集成。我猜想，你最好使用时间表作为矩阵来工作。

我的解决方案是用Ruby编写的，但这个概念也适用于其他语言。

这将允许您找到自由时间的单独块，但选择2-4小时，您将得到以下内容，以便一目了然：

[ 1 , 1 , 1 ], 
[ 1 , 1 , 1 ], 
[ 1 , 1 , 1 ], 

这可以在以后进行更高级搜索和实现算法时非常有用。对于这个简单的解决方案，我将演示以下内容。

calendar = [ # 0 is free, 1 is busy
  [ 1 , 1 , 1 ], #12AM to
  [ 1 , 1 , 1 ], #1AM to
  [ 1 , 1 , 1 ], #2AM to
  [ 1 , 1 , 1 ], #3AM to
  [ 1 , 1 , 1 ], #4AM to
  [ 1 , 1 , 0 ], #5AM to
  [ 1 , 1 , 0 ], #6AM to
  [ 1 , 1 , 0 ], #7AM to
  [ 1 , 1 , 0 ], #8AM to
  [ 0 , 1 , 1 ], #9AM to
  [ 0 , 1 , 1 ], #10AM to
  [ 1 , 1 , 1 ], #11AM to
  [ 1 , 1 , 1 ], #12PM to
  [ 1 , 0 , 1 ], #1PM to
  [ 1 , 0 , 1 ], #2PM to
  [ 1 , 0 , 1 ], #3PM to
  [ 1 , 1 , 0 ], #4PM to
  [ 1 , 1 , 0 ], #5PM to
  [ 1 , 1 , 1 ], #6PM to
  [ 1 , 1 , 1 ], #7PM to
  [ 1 , 1 , 1 ], #8PM to
  [ 1 , 1 , 1 ], #9PM to
  [ 1 , 1 , 1 ], #10PM to
  [ 1 , 1 , 1 ], #11PM to
  ["A","B","C"] #Users
  ]


def find_available_slot(length, calendar)
  [].tap do |results|
    calendar.transpose.collect do |schedule|
      times = schedule[0...-1]
      blocks = sort_it(times.each_index.select {|i| times[i] == 0 }).select { |x| x.count >= length }
      results << [blocks, schedule.last] unless blocks.empty?
    end
    results
  end
end

def sort_it(arr)
  tmp, main = [], []
  arr.each_with_index do |x, i|
    if arr[i-1]
      if arr[i-1] + 1 == x
        tmp << x
      else
        main << tmp unless tmp.empty?
        tmp = [x]
      end
    else
      tmp << x
    end
  end
  main << tmp
  main
end

find_available_slot(2, calendar)

对于我安排的示例日程，寻找有2小时可用的时间块，它返回以下结果：

=> [[[[9, 10]], "A"], [[[13, 14, 15]], "B"], [[[5, 6, 7, 8], [16, 17]], "C"]]

所以结果返回一个嵌套数组，数组的每个元素都是那些用户的块（如果有的话）。因此，result[0]将是第一个用户，result[0][0]将是块，result[0][1]将告诉您哪个用户。

这种调度矩阵在长期内非常强大，我建议您使用类似于2D的实现。

我进行了简短的谷歌搜索，您可以在这里阅读更多信息：

约会安排算法（N人与N空闲时段，约束满足）

在O(n)时间内查找重叠的约会？

http://www.geeksforgeeks.org/given-n-appointments-find-conflicting-appointments/

- OneNeptune