c++ - 一个时间区间内n个非重叠事件的随机调度

Question

如果这是一个众所周知的解决方案的众所周知的问题类别，请原谅我。我一直在寻找，但显然没有成功。

假设我有 n 个事件必须在一个时间间隔内发生(例如，[0,1])。每个事件都与从预定义分布中随机抽取的持续时间相关联。假设间隔远大于所有事件持续时间的总和:有效的时间表总是存在的。 [0,1]区间内事件发生的概率不均匀，但只要不重叠，事件就是独立的。

安排这些事件的有效且准确(随机)的方式是什么？

这是我当前的伪代码:

lowerBound = min(interval)upperBound = max(interval)for n in numEvents {  draw startTime   draw endTime  while ( startTime is less than lowerBound || endTime exceeds upperBound ) {    draw startTime    draw endTime  }  add event  reset lowerBound and upperBound to define largest remaining (event-free) interval}

我认为，通过选择更大的剩余时间间隔来安排新事件，我会让事件过度分散——比其他情况下的间隔更大。尽管如此，当事件数量较少时，这似乎非常有效并且可能非常准确。

我正在使用 C++，尽管这可能无关紧要。

如果您知道这类问题的名称，我也会非常感谢搜索词。

---

上下文:准确性对我来说是最重要的。在整个程序中，这不是一个耗时的步骤。

Answer 1

我只是随机放置每个事件，检查是否存在碰撞，如果发生碰撞，请将记录擦干净并重新开始。

你说间隔比事件持续时间的总和大得多，所以碰撞会很少见，所以这种方法在实践中是相当快的。

你说你想要准确的结果。我不确定这意味着什么，但我猜测我会说所有有效的解决方案都应该是同样可能的；问题中的当前解决方案不满足该要求，但这个解决方案满足。