临时将项目分配给人员并处理分配重组的算法

Question

假设我们有三台设备借给人们，用于他们要求的日期。当前程序会在用户请求时自动为他们分配设备 ID。该算法的工作方式是首先检查所有设备的状态，看看是否有任何“未请求”的设备。如果是这样，它只会将其分配给请求的人。

如果在特定时间段内请求了所有设备，它将检查是否有任何设备的请求日期与新请求不重叠。如果是这样，它将请求该设备。

我想编写另一种算法，在可以更有效地分配设备的情况下运行。例如:

Device 1: ####--##---######
Device 2: ----###-###------
Device 3: ---##---####-----

现在假设另一个用户出现并提出了对设备的请求，如下所示:

Device #: --------####-----
Device 1: ####--##---######
Device 2: ----###-###------
Device 3: ---##---####-----

在当前系统下，他们运气不好，因为在那个时间段没有可用的设备。但是，如果算法能够查看这三个设备，它可以将预订从设备 2 移动到设备 1 上的空位，然后通过给它们设备 2 来填充请求，最终看起来像:

Device 1: ####--###########
Device 2: ----###-####-----
Device 3: ---##---####-----

假设单个请求不能跨越多个设备，我将如何重新组织这些请求？

Answer 1

怎么样

initialize device end times to 0 (or some non-zero time if the device is in use)
sort the intervals by end time
for each interval
{
   assign the interval to the device
     a) whose end time is less than the interval start time (no overlap)
     b) has the minimum gap between the device end time and the interval start time
   update the device end time
}

使用问题中的示例，间隔(按结束时间排序)为:

1 - [1,4]
2 - [4,5]
3 - [5,7]
4 - [7,8]
5 - [9,11]
6 - [9,12]
7 - [12,17]

算法会像这样将间隔分配给两个设备

time:     12345678901234567
Device 1: 1111333-6666-----
Device 2: ---22-44555777777

间隔 1 可以分配给任一设备。由于无重叠规则，分配了间隔 2、3 和 4。间隔 5 是根据最小间隙规则分配的。然后根据无重叠规则分配 6 和 7。