Solution with O(n * m * logn) complexity is too slow? Probably we should sort faster?
Challenge. Can you solve the problem with n, m ≤ 106?
Let's elaborate, when a segment can become a train carriage.
Try to use dynamic programming on prefix.
Challenge. Can you solve the problem with n, a[i] ≤ 105? Try to use the fact, that .
Try to solve problem, when buttons can't be broken.
Try to find out whether the buttons are broken somehow, without taking risk of losing.
Challenge. Assume this problem: let's change all dangerous cells on walls, i.e such cells, in which it is just impossible to enter. Now you have to generate such string from moves 'L', 'R', 'U', 'D', that without dependance on possible button breakage of pairs 'L'/'R' and 'U'/'D', as in original problem, will visit finish cell. Of course, it is not necessary to stop at finish cell, you just have to visit it at least once.
Try to use interval tree.