代码之家 › 专栏 › 技术社区 › Kenta

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

organization sorting algorithm

1

Kenta · 技术社区 · 6 年前

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

如果所有设备都被请求了一段时间,它将检查是否有任何设备的请求日期与新请求不重叠。如果这是真的,它将对该设备提出请求。

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

现在让我们假设另一个用户出现并请求一个设备,该设备按如下方式排列:

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

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

如果一个请求不能跨越多个设备,我将如何重新组织这些请求?

2 回复 | 直到 6 年前

1

0

user3386109 6 年前

怎么样

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。

2

-1

Tamás Zahola 6 年前

如果有人请求设备间隔(a,b),请从设备1开始,并在(a,b)期间检查其是否可用。从设备1空闲的(a,b)中减去这些间隔,并将其标记为这些时间段的间隔。如果原始时间间隔中没有剩余的时间间隔,则完成;否则继续使用设备2和剩余的时间间隔(可能还有多个不相交的间隔!).

当然,这可能意味着一个给定的请求将由多个设备完成,因此,例如,如果我想租用一个设备一周,我可能必须从周一到周三使用设备1,然后将其返回并从周三到周五使用设备2。