算法找到最大的空闲时隙期的中间？ [英] Algorithm to find middle of largest free time slot in period?
问题描述
说我想安排在此期间00事件的集合：00-00：59。我安排他们在全分钟（00:01，从来没有〇时零一分30秒）。
Say I want to schedule a collection of events in the period 00:00–00:59. I schedule them on full minutes (00:01, never 00:01:30).
我要的空间出来，远地在该期间内，但我不知道事先我会多少事件小时内共有。我今天可能安排一个事件，然后两个明天。
I want to space them out as far apart as possible within that period, but I don't know in advance how many events I will have total within that hour. I may schedule one event today, then two more tomorrow.
我有我的头明显的算法，我能想到的暴力方式来实现它，但我敢肯定有人知道一个更好的方式。我想preFER红宝石或东西我可以转化为Ruby的，但我会采取什么我可以得到的。
I have the obvious algorithm in my head, and I can think of brute-force ways to implement it, but I'm sure someone knows a nicer way. I'd prefer Ruby or something I can translate to Ruby, but I'll take what I can get.
所以，该算法我能想到的在我的脑海：
So the algorithm I can think of in my head:
1事件刚刚结束了在00:00。
Event 1 just ends up at 00:00.
事件2结束了在00:30，因为那个时候是从现有的事件最远。
Event 2 ends up at 00:30 because that time is the furthest from existing events.
事件3可能最终在任00:15或00:45。所以，也许我随便挑了第一个，零点15分。
Event 3 could end up at either 00:15 or 00:45. So perhaps I just pick the first one, 00:15.
事件4，然后在00:45结束。
Event 4 then ends up in 00:45.
事件5结束了某处大约00:08（从○时○七分30秒四舍五入）。
Event 5 ends up somewhere around 00:08 (rounded up from 00:07:30).
等等。
因此，我们可以看到每对采取分钟（例如，00：00-00：15，00：15-00：30，00：30-00：00），挑最大范围（00：30- 00:00），由两个圆分吧。
So we could look at each pair of taken minutes (say, 00:00–00:15, 00:15–00:30, 00:30–00:00), pick the largest range (00:30–00:00), divide it by two and round.
但我敢肯定，这是可以做到更好。请分享！
But I'm sure it can be done much nicer. Do share!
推荐答案
您可以使用位反转来安排您的活动。只要看看你的事件的序列号的二进制重新presentation，扭转其位，然后将结果扩展到给定的范围（0到59分钟）。
You can use bit reversing to schedule your events. Just take the binary representation of your event's sequential number, reverse its bits, then scale the result to given range (0..59 minutes).
这是另一种方法是，以产生为了位反转字（0000,1000,0100,1100，...）。
An alternative is to generate the bit-reversed words in order (0000,1000,0100,1100,...).
这使得分发多达32个事件很容易。如果需要更多的事件，缩放后的结果，你应该检查是否生成的分已经被占用，如果是的话，生成和规模下一个字。
This allows to distribute up to 32 events easily. If more events are needed, after scaling the result you should check if the resulting minute is already occupied, and if so, generate and scale next word.
下面是在Ruby中的例子：
Here is the example in Ruby:
class Scheduler
def initialize
@word = 0
end
def next_slot
bit = 32
while (((@word ^= bit) & bit) == 0) do
bit >>= 1;
end
end
def schedule
(@word * 60) / 64
end
end
scheduler = Scheduler.new
20.times do
p scheduler.schedule
scheduler.next_slot
end
产生以位反转字
方法是从借来的事宜计算 ，章1.14.3。
Method of generating bit-reversed words in order is borrowed from "Matters Computational ", chapter 1.14.3.
更新：
由于缩放从0..63 0..59到该算法往往只是后0到使最小的槽，15，30，和45的问题是：它总是开始填充间隔从这些（最小）插槽，而它更自然，开始从大槽填充。算法是因为这个不完美的。另一个问题是需要检查已占用的分钟。
Due to scaling from 0..63 to 0..59 this algorithm tends to make smallest slots just after 0, 15, 30, and 45. The problem is: it always starts filling intervals from these (smallest) slots, while it is more natural to start filling from largest slots. Algorithm is not perfect because of this. Additional problem is the need to check for "already occupied minute".
幸运的是，一个小的修复将删除所有这些问题。只要修改
Fortunately, a small fix removes all these problems. Just change
while (((@word ^= bit) & bit) == 0) do
到
while (((@word ^= bit) & bit) != 0) do
和初始化 @word 63（或跟上0初始化它，但做一次迭代来获得的第一个事件）。此修复程序递减63的反向字为0，它总是事件分发到尽可能大的插槽，并允许没有冲突事件的第60次迭代。
and initialize @word with 63 (or keep initializing it with 0, but do one iteration to get the first event). This fix decrements the reversed word from 63 to zero, it always distributes events to largest possible slots, and allows no "conflicting" events for the first 60 iteration.
其他算法
在previous的方法很简单，但它只能保证（随时）最大的空槽不超过两次一样大的最小的插槽多。既然你要空间的事件，远越好，算法，基于斐波那契数或黄金比例，可能是preferred：
The previous approach is simple, but it only guarantees that (at any moment) the largest empty slots are no more than twice as large as the smallest slots. Since you want to space events as far apart as possible, algorithm, based on Fibonacci numbers or on Golden ratio, may be preferred:
- 将初始间隔（0..59）优先级队列（最大堆，优先级=间隔大小）。
- 要安排一个事件，弹出优先级队列，拆分所产生的间隔金比例（1.618），用分割点的时间，本次活动，并把两个结果的时间间隔回优先级队列。
这保证了最大的空槽不超过（约）1.618倍为最小插槽。对于较小的槽近似恶化和大小都与作为2：1
This guarantees that the largest empty slots are no more than (approximately) 1.618 times as large as the smallest slots. For smaller slots approximation worsens and sizes are related as 2:1.
如果不方便让计划更改的优先级队列，您可以prepare的60个可能的事件提前一个数组，此数组每次你需要一个新的事件时提取下一个值。
If it is not convenient to keep the priority queue between schedule changes, you can prepare an array of 60 possible events in advance, and extract next value from this array every time you need a new event.
这篇关于算法找到最大的空闲时隙期的中间？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
