优化匹配事件的结束日期与另一活动开始日期 [英] Optimization for matching End Date of an Event with Start Date of another Event

问题描述

我有事件（开始日期，结束日期，地点）的数据集。这些活动将在全国，我需要找出哪些事件就结束之后应该去的地方。

I have a data set of events (start date, end date, location). These events move in the country and I need to figure out which event should go where after it ends.

例：

1. [1/7，6/7，多伦多（启动7月1日，结束月6日）
2. [2/7，4/7，蒙特利尔]
3. [4/7，11/7，渥太华]
4. [17/7，22/7，温哥华]

...等（数据集将围绕100个条目，所以性能是不是一个真正的问题）

..etc (Data set will be around 100 entries, so performance is not really an issue)

在本例，事件1可以移动，做事件4，因为它结束于七月六日和事件4开始的第17位。 （在同一天假设过境）

In this exemple, Event 1 could move and do Event 4, since it ends on the 6th of July and Event 4 starts on the 17th. (Assuming transit in the same day)

所有事件无法找到合适的比赛将被存储在一个报告有人手动匹配。

All Events that couldn't find a suitable match will be stored in a report for someone to match manually.

此优化code将用JavaScript来实现。

This optimization code will be done in javascript.

我的第一个念头是有2个阵列，使用相同的数据。第一个数组排序开始日期，第2个数组排序结束日期。然后通过结束日期的列表，并试图找到一个合适的开始日期，然后从数组中删除这些条目，并继续这样，直到没有更多的匹配是可能的。

My first thought was to have 2 arrays, with the same data. First array sorted by Start Date, 2nd array sorted by End Date. Then go through the list of End Dates and try to find an appropriate Start Date for it, then remove these entries from the array and continue like that until no more matching is possible.

任何人对如何处理这个问题的一个更好的主意吗？如果您需要更多的细节让我知道！

Anybody has a better idea on how to approach this problem ? If you need more details let me know!

推荐答案

你的问题不是很清楚。如果我理解正确的话，你的目标是选择事件的一个子集，使得您的选择最大化事件的数量（也有不重叠的事件）。如果是这样，您的问题可以被看作是一个活动选择问题的。有一个简单的贪心算法来解决。

Your question isn't very clear. If I understand correctly, your goal is to choose a subset of events such that your selection maximizes the number of events (and there are not overlapping events). If so, your problem can be seen as an Activity Selection Problem. There is a simple greedy algorithm to solve that.

让

event[1..n] the n events
start[i] the start time of the event number i
finish[i] the finish time of the event number i

和假设你已经按结束时间排序的事件。

and assume that you already sorted the events by end time.

下面的贪心算法会发现在最大的子集的取值的非重叠事件： （注意， LSE 的是最后选定事件的）

The following greedy algorithm will find the largest subset S of non overlapping events: (note that lse is the Last Selected Event)

S = {event[1]}
lse = 1

foreach event[i] do:
     if start[i] > finish[lse]:
         S = S + {event[i]}
         lse = i

return S

基本上是：

1. 您按结束时间的事件排序
2. 您选择的第一个事件
3. 您环路上的事件，贪婪地选择第一一个不与最后一个重叠的选择

这篇关于优化匹配事件的结束日期与另一活动开始日期的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！