Can't find an optimal solution to this problem and not sure what exact wording to search for.
I'm trying to come up with an algorithm that will propose what a journey will look like.
The input will be something like:
For each leg of a trip: date, departure and arrival times, duration, when you get on and off.
The input will be a list of such trips. We don't exactly know the first point where we get on and last point we get off.
I need to be able to show in a way that makes sense in a complete journey such as:
07:00 - 08:00 - 2/10/2018 - New York - Boston - 1:00 Hour 09:15 - 13:00 - 2/10/2018 - Boston - London - 3:45 Hour 13:10 - 14:10 - 2/10/2018 - London - Paris - 1:00 Hour 15:00 - 17:00 - 2/10/2018 - Paris - Moscow - 2:00 Hour
The initial input will be the above in a vector in a random order. There may be "extra" trips that will not be used but have been booked by mistake ie:
08:15 - 12:00 - 2/10/2018 - Boston - London - 2:45 Hour
(this one is not desired as there is more time to wait in London - we want the least amount of time on the ground waiting)
Any tips on how to approach this?
I have tried sorting the list then going through a loop and connecting them but it fails corner cases where there are two similar journeys such as the above.
Any help is appreciated.