java - Cars and gaps In Traffic-Hacker rank

Question

Can you please help me to solve the following program which was asked recently in one of the off-campus interviews...

problem statement: Given a 2 lane road with n positions and a total number of m cars moving from left to right, from a start position to finish, determine the largest gap in positions of all cars, without regard to lanes.

Example:

n=10

start=[1,2,5,8]

finish=[2,2,6,10]

This above depicts a road n=10 units in length with cars m=4 cars:

1.The first car spans from position start[0]=1 to position finish[0]=2

2.The second car spans from position start[1]=2 to position finish[1]=2

3.The third car spans from position start[2]=5 to position finish[1]=6

4.The fourth car spans from position start[3]=8 to position finish[3]=10

5.There are gaps at positions 3-4 and 7. The largest gap between cars is 2.

Function Description Complete the function WidestGap in the editor below

WidestGap has the following parameters(s): int n: the length of the road section int start[m]: the positions of the rear of each car int finish[m]: the positions of fronts of each car

Return int: the length of the largest gap between cars.

constraints -> 1<=n<=10^9

-> 1<=m<=10^5

-> 1<=start[i]<=finish[i]<=n, where 0<=i<m

sample input

STDIN Function

---

10 -> n=10

2 -> start[] size m=2

3 -> start = [3,8]

8

2 -> finish[] size m=2

4 -> finish = [4,9]

sample output

3

Explanation This above depicts a road n=10 units in length with cars m=2 cars:

1.The first car spans from position start[0]=3 to position finish[0]=4

2.The second car spans from position start[1]=8 to position finish[1]=9

NO cars in positions[1,2], positions [5,6,7] or position [10].The largest gap between cars is 3.

Code Snippet

public static int WidestGap(int n, List<Integer> start, List<Integer> finish){
// write your code here
}

Appreciate any feedback you may give,

Thank you

question from:https://stackoverflow.com/questions/65662082/cars-and-gaps-in-traffic-hacker-rank

Answer 1

I have tried python solution for this, tested in some cases got correct answer, cannot say if it is completely correct or not.

Solution:

def WidestGap(n, start, finish):
    maxgap = 0
    i = 1
    min_start = 0
    while i < len(start):
        if finish[min_start] > start[i] and start[i] < start[min_start]:
            maxgap = 0
            min_start = i
        elif finish[min_start] < start[i]:
            maxgap = max(maxgap, (start[i] - finish[min_start]) -1)
            min_start = i
        i +=1
    if (n - max(finish)) > maxgap:
        maxgap = n - max(finish)
    if min(start) -1 > maxgap:
        maxgap = min(start) -1
    return maxgap

please let me know any failed test cases and if any better approach.