1

设想：

我需要让用户有机会为服务预订不同的时间。需要注意的是，我没有提前预订，但我需要在他们进来时填写。

预订可以表示为键值对：

[startTime, duration]

因此，例如，[9,3]这意味着事件从 9 点开始，持续时间为 3 小时。

规则：

  • 用户一个接一个进来，从来没有一批用户请求
  • 没有预订可以重叠
  • 24/7 全天候服务，因此无需担心“工作时间”</li>
  • 用户duration自行选择
  • 显然，一旦用户选择并确认他的预订，我们就不能再洗牌了
  • 我们不希望差距小于某个时间。这是基于未来用户填补空白的概率。例如，如果durations超过用户预订的分布使得未来用户填补短于x小时的差距的概率小于，p那么我们需要一个规则，即差距不能短于x。（出于这个问题的目的，我们可以假设x是硬编码的，这里我只是解释一下原因）
  • 目标是最大化服务忙碌持续时间

到目前为止我的想法...

  1. 我保留了到目前为止的预订清单
  2. 我还跟踪差距（因为它们是新用户预订的潜在位置）
  3. 当新用户预订时，[startTime, duration]我首先检查理想情况gapLength = duration。如果没有这样的间隙，我会找到满足条件的所有插槽（间隙）并按该值gapLength - duration > minimumGapDuration降序排列它们gapLength - duration
  4. 我将用户分配给最大值为的第一个空白，gapLength - duration因为这使我在此预订后剩余的空白也将在未来被填补的可能性最高

问题：

  1. 我的方法是否存在一些我遗漏的问题？

  2. 是否有一些算法可以解决这个特定问题？

  3. 是否有一些我可以开始并稍后优化的常用方法（良好的起点）？（我实际上是在尝试获得足够的信息来开始，但没有犯一些严重的错误；优化可以/应该稍后进行）

PS。从目前的研究来看，这听起来可能是约束规划的情况。如果可能的话，我想避免它，因为我对此一无所知（也许它很简单，我只是不知道），但如果它产生了真正的影响，我会争取它的好处并实施它。

我通过stackoverflow解决了类似的问题，但没有找到未来事件未知的问题。如果有这样的，这是直接重复的，请参考它。

4

0 回答 0