Running routes
Solutions This problem looks like a classical puzzle: merging overlapping intervals.
A naive approach is \(O(N^2)\) and consists in checking each route with the others. In case they overlap, remove the other route from the array and merge both into the first one.
The crucial condition to check if two routes overlap is (assuming route1 precedes route2):
1 route1.end >= route2.begin For example:
1 2 3 1 5 3 6 10 32 1 5 overlaps with 3 6, indeed 5 >= 3.
[Read More]