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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.