Details:

• There are two cities, a, b. and two arrays representing flight departure time.

• Flight from a to b is represented using array a2b, and flight from b to a is represented using array b2a.

• Flight from a to b and b to a both take 100 minutes.

• Need to take "n" roundtrips between the two cities(a -> b and b -> a is ONE round trip).

• Assume you always take the first flight from a to b and then take the earliest available flights.

Question: Return the time you arrive back at city a.

Example:

a2b = [109, 500]
b2a = [210, 600]
n = 2(roundtrips we need to take)

Explanation:

• Take 109 from a to b, arrive at b at 109 100 = 209
• Take 210 from b to a, arrive at 210 100 = 310.
• Take 500 from a to b again.
• Arrive at b at 500 100 = 600, then take 600 flight back
• Arrive at a at 600 100 = 700.

My Code:

def flight_time(a2b, b2a, n):
    
    a2b.sort()
    b2a.sort()
    
    trips = 0
    a_arrival_time = 0
    
    i = j = 0
    while trips < n:
        b_arrival_time = a2b[i]   100
        i  = 1
        
        while j < len(b2a):
            if (b2a[j] - b_arrival_time) < 0:
                j  = 1
                continue
            else:
                a_arrival_time = b2a[j]   100
                j  = 1
                trips  = 1
                break
      
    return a_arrival_time      

flight_time(a2b, b2a, n)
            

The code is running fine for this use case but it looks like the code is not handling all the edge cases.

For example, I get IndexError: list index out of range when n becomes large such as n=6.

Kindly suggest a better way to resolve the same problem.

CodePudding user response：

Your code correctly checks that j identifies a departure at b that is possible, but the same check is not done for flights from a. Instead your code just assumes that i has a departure time that is possible. You should in fact use the exact same logic for both directions.

It is not defined in your question what the algorithm should return when the task is not possible, i.e. when at a certain moment there are no flights anymore that can be taken to complete the itenary. I'll assume that in that case a value of -1 should be returned.

Here is a solution that defines a function for a finding and executing a single flight. This can then be used to fly from a to b, and also to fly from b to a:

from bisect import bisect_left 

def flight_time(a2b, b2a, n):
    a2b.sort()
    b2a.sort()

    def first_flight(timetable, time):
        if time == -1:  # out of time
            return -1
        i = bisect_left(timetable, time)
        return timetable[i]   100 if i < len(timetable) else -1

    time = 0
    for _ in range(n): # Number of round trips
        time = first_flight(a2b, time)
        time = first_flight(b2a, time)

    return time

Note that I didn't bother to have an early exit when time becomes -1. In that case time remains -1 in the remaining iterations of the main loop. If you want you could detect this value in the main loop and exit it.

Secondly, I used bisect. This may or may not make the algorithm more efficient depending on how often flight times are to be skipped in a linear search.