Optimization to match the end date of an event with the start date of another event

Question

I have a set of event data (start date, end date, location). These events are moving in the country, and I need to find out what event should take place where it will end.

Exemple:

• [1/7, 6/7, Toronto] (starts July 1, ends July 6).
• [2/7, 4/7, Montreal]
• [4/7, 11/7, Ottawa]
• [17/7, 22/7, Vancouver]

.. etc. (the data set will be about 100 records, so performance is actually not a problem)

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

All events that cannot find a suitable match will be saved in the report for manual matching.

This optimization code will be executed in javascript.

My first thought was to have 2 arrays with the same data. The first array sorted by start date, the second array sorted by end date. Then go to the list of end dates and try to find a suitable start date for it, then delete these entries from the array and continue so that there are no more matches.

Anyone have a better idea on how to approach this problem? If you need more information let me know!

Answer 1

Your question is not very clear. If I understand correctly, your goal is to select a subset of events so that your choice maximizes the number of events (as well as non-overlapping events). If so, your problem may be considered as the task of choosing actions . There is a simple greedy algorithm for this.

Let be

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 suppose you have already sorted events by time .

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 

Basically:

• sort events by time
• you select the first event
• you focus on events, eagerly choose the first one that does not overlap with the last one you choose