# Schedule two trains whose tracks overlap so they don't crash

I've encountered scheduling problems in my algorithms class before like the type we use vertex cover to solve.

Recently I was asked this question and did not even know what algorithmic technique to use to answer it!

There are two trains, which run between stations and share a portion of track. For instance train 1 runs between stations A B C D E F G H and train 2 runs between stations I J K B C D E F L M so the trains share the track between B C D. At each end of the track the train turns around and goes the other way on its track. The trains go from station to station in 1 unit time. I need to prevent the trains from crashing head on on the shared track, I have the power to stop either train at any station and restart it again when I please.

How can I solve this problem without using a ton of if else clauses, what CS principles should I be using here?

edit

Some background, the first solution I wrote was just a simple check to see if the other train was on the shared track before sending the other train out. That seemed ad hoc to me and I'm sure it did to the company I interviewed for as well.

I figure there must be an algorithm or at least a school of thought for this type of problem, after all how do they build extensible systems for managing shared runway space at an airport, or managing traffic flow at stop lights.

My intuition is that this is a very introductory problem to a school of thought in computational problem solving I have not yet encountered.

I might be wrong, but could anybody clear the air for me?

• This problem is similar to mutual exclusion, with the common portion of tracks as a shared resource. One difference is that it is actually safe for both trains to be in the shared section if they are traveling in the same direction, provided that the trailing train is stopped at a station as long as the leading train has not yet left the next one. Commented Aug 21, 2015 at 14:55
• shane, you say nowhere in the question that all stations must be served, or how often. For instance, one trivially safe solution is to have train 1 run its track, and start 2 when 1 arrives. When 2 finishes, start 1 for its tour back, and so on. You do not exclude such solutions, so it's not clear what your question is. Commented Aug 21, 2015 at 16:23
• Hm, okay this was not noted in the original question either, however I assumed for practicality we want each train to run as much as possible (to avoid delays and provide good service). I understand now that this is a critical section, and perhaps the problem only goes as far as to identify what exactly the critical section is and block a train while that critical section is occupied, the critical section being when a train is on the critical section headed towards the other train. Perhaps this does not lend itself to such a discussion as I originally thought. Commented Aug 21, 2015 at 16:29
• If you're looking for related work, it's worth mentioning that train scheduling itself is a fairly large, widely-studied filed.
– SamM
Commented Feb 18, 2016 at 9:51

If you calculate the cycle, as there are only two trains and distance between every station is one, you could simply run them in order and appoint wait in some station to avoid crash.

If you have to implement some unfortunate events (first one stops for some reason, reschedule it to run on itd own time).

With two trains it will work without problems.

Otherwise use semaphores (it fits even literally ;)

There is no explicitly given synchronisation problem, so nasty trick works.

A related and well studied area is threading/multiprocessing. Your initial solution is a simple lock; the critical section of tracks can only be used by one train at a time. To extend this while avoiding deadlocks (two trains waiting in each other) or starvation (a train waits forever), you would want to use some more sophisticated locking mechanism and scheduler.

• This strikes me to be more of a comment than an answer. (Deadlocks clearly can't happen here, as every train can only ever wait on one shared portion of the track.) Commented Aug 21, 2015 at 8:13
• @Raphael His question seems to be, "What techniques are used on similar problems, specifically extending to larger systems like airports and traffic lights?" Commented Aug 21, 2015 at 16:06