The way I think of it, divide the tracks into segments. Before you put a train on a segment, you must ask a question - is there a train on it. There are only two answers possible, No, and something else. If it is something else, stop. Don't let the train on that segment.

There are optimizations possible like make segments smaller etc but the original algorithm is trivial. If we can't figure things out, we make segments longer and we slow down the trains until we can. I am positive for a sufficiently large track segment and a sufficiently slow train, we can always answer the question with a no.