In [1]:
# A Careful Approach
# Implement this code and play with it
# You don't have to type in all the comments...
# I am ignoring fractional minutes, and considering integer gaps only
import itertools
# This function tests a candidate gap time with a particular landing sequence
# inputs a landing sequence, the time window lists, and a gap time to test
def checkGap(order,A,B,gap):
# intialize t at start of the first plane's time window
t = A[order[0]]
# now step through the rest of the planes in the landing sequence
for plane in order[1:]:
# if the next landing time is beyond the next plane's landing window -> return False
if t+gap > B[plane]:
return False
else:
# otherwise, land the next plane after the gap time,
# or at the beginning of the plane's landing window,
# whichever time is greater
t = max(t+gap,A[plane])
# If you get to here, all planes have landed: THE GAP WORKED
return True
# This function uses Binary Search to find the maximum gap between landing times
# the mid value is tested for all permutations of plane landing sequences
# N <= 8, so it is possible to do a complete search on all 8! sequences
def gapBinarySearch(planeList,Beg,End):
p1 = 0
p2 = max(End)
while p1 <= p2:
mid = (p1 + p2)//2; # floor division
validPlan = False
for config in itertools.permutations(planeList):
validPlan = checkGap(config,Beg,End,mid)
print("Gap =",mid, "Landing Sequence =",config, "Gap Works =",validPlan)
if (validPlan):
bestGap = mid
p1 = mid + 1
break
if (not validPlan):
p2 = mid - 1
return bestGap
## Test data
N=3
testPlaneList = [x for x in range(N)]
testBeg = [0,5,10]
testEnd = [10,15,12]
bestGap = gapBinarySearch(testPlaneList,testBeg,testEnd)
print("Maximum Interval Between Landings =",bestGap)
