CODEWITHSUNDEEP
pythonpython-3.xlistalgorithmdata-structures
meallhour
meallhour

Reputation: 15571

Algorithm to calculate time intervals

Details:


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:


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.


Upvotes: 0

Views: 916

Answers (1)

trincot
trincot

Reputation: 350107

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.

Upvotes: 1

Related Questions