Найдите время, когда последний автомобиль достигнет конца пути в заданной гонке.

Дана гоночная трасса длиной N единиц. где каждый автомобиль движется со скоростью 1 единица в секунду. Даны два массива left[] и right[] , обозначающие позиции автомобилей, движущихся влево и вправо соответственно. Когда две машины, движущиеся в двух противоположных направлениях, встречаются в какой-то точке пути, они меняют свое направление и снова продолжают движение в обратном направлении. Возвращает время, когда последний вагон достигает любого из концов трассы.

Примечание: Изначально никакие две машины не стоят на одном и том же месте.

Примеры:

Input: N = 4, left = {4, 3}, right = {0, 1}
Output: 4
Explanation:
The car at index 0 is named A and going to the right.
The car at index 1 is named B and going to the right.
The car at index 3 is named C and going to the left.
The car at index 4 is named D and going to the left.
The last moment when a car was on the race track is t = 4 seconds. 
See the image given – 

Input: N = 7, left = {0, 1, 2, 3, 4, 5, 6, 7}, right = { }
Output: 7
Explanation: All cars are going to the left, the car at index 7 needs 7 seconds to reach the end of track.

Input: N = 10, left = {3, 5}, right = {1}
Output: 9
Explanation:
Say at t = 0, carA = 1 (->), carB = 3 (<-), carC = 5 (<-)
At t = 1: carA and carB collides at 2 and change directions. 
So, carA = 2 (<-), carB = 2 (->), carC = 4 (<-)
At t = 2, carB and carC collides at 3 and change direction.
So, carA = 1 (<-), carB = 3 (<-), carC = 3 (->)
At t = 3, carA reaches 0.
So, carA = 0 (<-), carB = 2 (<-), carC = 4 (->)
At t = 4, only carB and carC are running on track in opposite directions.
So, carB = 1 (<-), carC = 5 (->)
At t = 5, carB reaches at 0.
So, carB = 0 (<-), carC = 5 (->)
carC alone running towards right end (index 9).
So, at t = 9 carC reaches at 9.

Подход : Задача может быть решена на основе следующего наблюдения.
Поскольку автомобили при столкновении сразу же меняют направление и начинают двигаться в противоположном направлении, можно считать, что сталкивающиеся автомобили просто меняются местами и после этого движутся в том же направлении. Таким образом, требуемое время — это максимальное время, которое требуется любому автомобилю, чтобы добраться из начального положения до конечного, если он продолжает двигаться в том же направлении.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(M), где M — максимальный размер двух массивов.
Вспомогательное пространство: O(1)