Aircraft Spacing

Aircraft Spacing

This problem deals with airports and air traffic controllers. Specifically, we want to decide from a set of aircraft which ones to land and which ones to put on hold.

The air traffic controllers have quite a difficult job deciding which aircrafts to put on hold and which ones to land.

Problem Statement

When an aircraft is flying through the air, it leaves behind wake turbulence—unstable air that causes any following aircraft to have a very bumpy ride.

The turbulence is usually generated from doing tips and is sometimes called wingtip vertices. The clouds behind the wingtips of the aircraft are swirling around as the aircraft passes through them.

Due to this effect, the air traffic controllers have to leave quite some spacing behind each aircraft so the preceding aircraft can land safely.

This means that during a busy time, they need to put some of these aircraft on hold and let others land. That's what this problem seeks to solve: We need to come up with an algorithm that decides which aircraft should land and which should be put on hold so that they can land later safely.

Solution: Aircraft Spacing Recursive

class AircraftSpacing:

	def __init__(self, nums) -> None:
		self.nums = nums

	def maxPass(self):
		return self.max_pass_rec(self.nums)

	def max_pass_rec(self, nums):
		if len(nums) == 0:
			return 0
		i = 0
		return max((nums[i]+ self.max_pass_rec(nums[i+2:])), self.max_pass_rec(nums[i+1:]))

nums =[155, 55, 2, 96, 67, 203, 3]
print(" Aircraft Spacing Rec:: ", AircraftSpacing(nums).maxPass())

Code Walk Through

The code shows a class AircraftSpacing that takes a list of integers (nums) as input. The class has a method maxPass which calls a recursive helper method max_pass_rec to find the maximum possible sum of integers. 

The constraint is that no two adjacent integers can be included in the sum.

Here's a step-by-step breakdown of the code:

In this code, I tried running with the following list,

Unfortunately, the algorithm could not complete & return the results as is the case with the first list above.

Time Complexity Analysis

 The time complexity of the recursive function is exponential, specifically O(2^n), where n is the length of the input list.

This is because, in each recursive call, two branches are explored, leading to an exponential number of recursive calls.

There are suggestions to indicate that this function is super-exponential almost matching the factorial algorithm.

However, the function has overlapping subproblems and the same subproblems are solved multiple times.

As a result, memoization or dynamic programming techniques can applied to optimize the time complexity.

Space Complexity Analysis

The space complexity is O(n), where n is the length of the input list. This is because the depth of the recursion can go up to n, and at each level of the recursion, a constant amount of space is used for variables like i.

Solution: Aircraft Spacing Top-Down

class AircraftSpacingTopDown:

	def __init__(self, nums) -> None:
		self.nums = nums
		self.dp ={}

	def maxPass(self):
		return self.max_pass_rec(self.nums)

	def max_pass_rec(self, nums):
		if len(nums) == 0:
			return 0
		if len(nums) in self.dp:
			return self.dp[len(nums)]
		
		i = 0
		self.dp[len(nums)]=max((nums[i]+ self.max_pass_rec(nums[i+2:])), self.max_pass_rec(nums[i+1:]))
		return self.dp[len(nums)]
	
nums =[155, 55, 2, 96, 67, 203, 3]
nums =[155, 55, 2, 96, 203, 3, 66, 32, 65, 29, 8, 299, 323, 77, 3, 28, 128, 19, 523, 372, 2, 3, 66, 124, 38, 34, 12, 88, 23, 74, 65, 87, 434, 14, 7, 49, 38, 27, 641, 61, 58, 14, 57, 71, 11, 82, 178, 93, 191, 4]
print(" Aircraft Spacing Top Down:: ", AircraftSpacingTopDown(nums).maxPass())

The Top-down approach otherwise called memoization returns results for our longer list that the recursive function was unable to return.

The solution I have provided here uses a top-down dynamic programming approach with memoization to optimize the recursive solution. Let's analyze the time and space complexity.

Time Complexity

•     The function max_pass_rec is a recursive function with memoization.
•     The time complexity is O(n), where n is the length of the input list nums.
•     This is because each subproblem is solved only once, and the result is stored in the self.dp dictionary. When you encounter a subproblem with a length that has already been memoized, the function retrieves the result in constant time.

Space Complexity

•     The space complexity is also O(n).
•     The primary contributor to the space complexity is the memoization table self.dp, which stores the results of subproblems.
•     In the worst case, where all unique subproblems need to be memoized, the size of the memoization table would be proportional to the length of the input list numbers.
•     The recursive call stack contributes O(n) space in the worst case, as the depth of the recursion can go up to the length of the input list.

Overall, the top-down dynamic programming solution with memoization significantly improves the time complexity compared to the naive recursive solution by avoiding redundant computations of subproblems.

The space complexity is also reasonable and efficient.

Solution: Bottom-Up Solution

class AircraftSpacingBottomUp:

	def __init__(self, nums) -> None:
		self.nums = nums
		self.dp =[0 for i in range(len(nums) + 2)]

		if len(nums) == 0:
			return 0
			
		if len(nums) in self.dp:
			return self.dp[len(nums)]
		for i in range(len(nums)-1, -1, -1):
			res = max(nums[i]+ self.dp[i+2], self.dp[i+1])
			self.dp[i]=res

	def maxPass(self):
		return self.dp[0]

nums =[155, 55, 2, 96, 67, 203, 3]
nums =[155, 55, 2, 96, 203, 3, 66, 32, 65, 29, 8, 299, 323, 77, 3, 28, 128, 19, 523, 372, 2, 3, 66, 124, 38, 34, 12, 88, 23, 74, 65, 87, 434, 14, 7, 49, 38, 27, 641, 61, 58, 14, 57, 71, 11, 82, 178, 93, 191, 4]
print(" Aircraft Spacing Bottom up:: ", AircraftSpacingBottomUp(nums).maxPass())

Time Complexity

The time complexity of the provided bottom-up dynamic programming solution is O(n). This is because the solution iterates through the input list nums once in reverse order, and at each step, it computes and stores the maximum sum in the self.dp array.

The iteration only takes a linear time for the length of the input list.

Space Complexity

The space complexity of the provided solution is O(n). Here's the breakdown:

The bottom-up dynamic programming solution is efficient in terms of both time and space complexity, as it avoids recursion and uses an array to store results iteratively.

The space complexity is linear, and the time complexity is also linear, making it a more optimized solution compared to the naive recursive approach.

Solution: Optimized Bottom-up Dynamic Programming

class AircraftSpacingBottomUpOpt:

	def __init__(self, nums) -> None:
		self.nums = nums
		self.first, self.second =0, 0

		if len(nums) == 0:
			return 0

		for i in range(len(nums)-1, -1, -1):
			temp = max(nums[i]+ self.second, self.first)
			self.second = self.first
			self.first = temp
			

	def maxPass(self):
		return self.first

nums =[155, 55, 2, 96, 67, 203, 3], 0, 0
nums =[155, 55, 2, 96, 203, 3, 66, 32, 65, 29, 8, 299, 323, 77, 3, 28, 128, 19, 523, 372, 2, 3, 66, 124, 38, 34, 12, 88, 23, 74, 65, 87, 434, 14, 7, 49, 38, 27, 641, 61, 58, 14, 57, 71, 11, 82, 178, 93, 191, 4]
print("Optimized Aircraft Spacing Bottom up:: ", AircraftSpacingBottomUpOpt(nums).maxPass())

Time Complexity

The time complexity of the optimized bottom-up dynamic programming solution is O(n). It iterates through the input list numbers once in reverse order, and at each step, it updates the variables self.first and self.second.

The iteration takes a linear time for the length of the input list.

Space Complexity

The space complexity of the provided solution is O(1). That's to say, the solution uses a constant amount of extra space. It doesn't rely on an additional array or data structure to store intermediate results.

Since the space complexity is constant, it is a more optimized solution compared to solutions that use additional arrays or tables to store intermediate results.